【题目描述】

作为一位OIer，小明既要学OI，又要不落下文化课，学文化课的时候想要学OI,学OI的时候想要学文化课.为了解决矛盾,他决定以周为单位安排文化课和OI的学习.例如:学1周文化课,学1周OI,学1周文化课,学2周OI,学2周文化课……。 　　 距离CSP2021考试还有N周.他想合理安排这N周的学习内容使得自己的知识水平在N周之后尽量高. 一个人的OI水平LevelOI和文化课水平LevelWHK的乘积等于知识水平LevelZS.具体来说,LevelOI和LevelWHK都是一个整数,而LevelZS=LevelOI*LevelWHK.

在这N周之前,小明太颓了,故一开始他的OI水平为0,文化课水平为0.在第i周,如果他学习文化课,他的文化课水平提高ai,OI水平降低bi;如果他学习OI,他的OI水平提高ci,文化课水平降低di.OI水平和文化课水平的最大值没有限制,但最低不会小于0.即,如果OI水平/文化课水平不足x的时候减少了x,那么将变为0而不是一个负数.

小明现在,求不出他能够达到的最高知识水平,于是造了个题出到模拟测试里,要选手求出他能够达到的最高的知识水平LevelZS.

【输入格式】

第一行一个整数N

接下来N行每行4个空格隔开的整数ai,bi,ci,di.

【输出格式】

一行一个整数表示答案.

【样例输入】

2
666 233 666 233
666 233 666 233

【样例输出】

288378

【数据范围】

前4个测试点满足:对于第i个测试点,N=i

第5个测试点满足:所有bi=0,所有di=0,所有ai=1,所有ci=1

第6个测试点满足:所有bi=1,所有di=1,所有ai=1,所有ci=1

全部数据,1<=N<=15,0<=ai,bi,ci,di<=1000000