背景 Background

xiaoT发现山谷相当的大，准确地说应该是相当的长，xiaoT想到山谷的那头去看看，但是靠xiaoT走路的速度，到那边要n年。还好xiaoT可以买一些苹果（？？苹果买苹果？？自相残杀or大义灭亲），它把这些苹果当成动力，根据火箭发射的原理（晕，这个苹果知道得真多），如果xiaoT把苹果向后扔，xiaoT就会向前进（Q:xiaoT能把苹果扔多远？A:xiaoT拥有超强的臂力。Q:xiaoT怎么会有手呢？A:...）。

描述 Description

苹果有两种，一种青苹果，一种红苹果。

已知到山谷的长度为k，用一些（同一种类）苹果可以通过的路程为1。

苹果的价格是不一样的，红苹果的价格是红苹果个数的四次方。

青苹果的价格就是青苹果个数。

输入格式 Input Format

第一行k表示山谷的长度。

接下来k行，每行两个正整数，分别表示通过该段：

如果使用红苹果，则需要的数量为a

如果使用青苹果，则需要的数量为b

输出格式 Output Format

输出只有一个数，买苹果的最少的花费。

样例输入 Sample Input

3
3 1000
2 5000
4 8000

样例输出 Sample Output

2296

样例解释

第1段用青苹果，第2、3段用红苹果，花费是1000+(2+4)^4

数据规模

对于30%的数据，k≤10

对于50%的数据，k≤25

对于100%的数据，k≤50

对于100%的数据，每段路消耗的红苹果的数量≤10

对于100%的数据，每段路消耗的青苹果的数量≤10^7