Treasure in the Diamond Factory

wrzSama is on a treasure hunt and accidentally falls into a magical room containing n machines. The i-th machine produces \(2^{i}\) diamonds per use. Specifically, when wrzSama operates the i-th machine for the first time it takes \(a_i\) time and yields \(2^{i}\) diamonds. Each time the machine is used, its operating time increases by \(b_i\). That is, the x-th use of machine \(i\) takes \(a_i+(x-1)b_i\) time.

wrzSama needs at least \(2^{n}\) diamonds to obtain the treasure. Find the minimum total time required to accumulate at least \(2^{n}\) diamonds.

inputFormat

The first line contains an integer \(n\) representing the number of machines.

Each of the following \(n\) lines contains two integers \(a_i\) and \(b_i\) (for \(i=1,2,\dots,n\)), where \(a_i\) is the initial operating time and \(b_i\) is the additional time incurred in subsequent operations of the i-th machine.

outputFormat

Output the minimum time required to obtain at least \(2^{n}\) diamonds.

sample

3
3 1
2 1
10000 10000

5