Background

Description

退役之后,liu_runda总会想起学OI的时候自己怎样被郭神虐爆…
liu_runda学文化课的时候想要学OI,学OI的时候想要学文化课.为了解决矛盾,他决定以周为单位安排文化课和OI的学习.例如:学1周文化课,学1周OI,学1周文化课,学2周OI,学2周文化课…
距离他退役还有N周.他想合理安排这N周的学习内容使得自己的知识水平在N周之后尽量高. 一个人的OI水平LevelOI和文化课水平LevelWHK的乘积等于知识水平LevelZS. 具体来说,LevelOI 和 LevelWHK 都 是 一 个 整 数 , 而LevelZS = LevelOI * LevelWHK.
在这N 周之前,liu_runda 太颓了,故一开始他的 OI 水平为0,文化课水平为0.在第i周,如果他学习文化课,他的文化课水平提高ai,OI水平降低bi;如果他学习OI,他的OI水平提高 ci,文化课水平降低 di.OI 水平和文化课水平的最大值没有限制,但最低不会小于0.即,如果OI水平/文化课水平不足x的时候减少了x,那么将变为0而不是一个负数.
liu_runda 现在实在是太咸鱼了,求不出他能够达到的最高知识水平,于是造了个题出到联考里,要选手求出他能够达到的最高的知识水平LevelZS.

Format

Input

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

Output

一行一个整数表示答案.

Sample

Input

2 
666 233 666 233 
666 233 666 233 

Output

288378 

Limitation

前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
1s, 512000KiB for each test case.

Hint

Source

CDQZ TEST