Не всё спокойно в Найт-Сити. Грабитель ограбил банк, который находится в n-этажном доме, и теперь пытается сбежать с помощью вертолёта на крыше. Этажи в доме пронумерованы от 0 до n - 1, а крыша считается этажом номер n. Сейчас правоохранительные органы находятся на нулевом этаже, вместе с грабителем.

У грабителя есть особый чип, который позволяет ему вырубать полицейских роботов в тот момент, когда грабитель и полиция оказываются одновременно на одном этаже. Эффективность чипа зависит от электрических полей этажа, на котором он был использован. А именно, если, находясь на i-м этаже, грабитель использовал чип k раз (k целое положительное число), то на это израсходуется k * qi единиц энергии, а полиция будет остановлена на k * ti минут, и только после этого продолжит движение.

Грабитель поднимается со скоростью один этаж в минуту, а его преследователи поднимаются со скоростью два этажа в минуту. Каждый раз, когда полиция и грабитель оказываются одновременно на одном этаже, грабитель обязан использовать чип хотя бы один раз, иначе полиция его схватит. Если полиция догонит грабителя между этажами, он не сможет воспользоваться чипом и будет схвачен.

Чтобы безопасно покинуть здание, грабитель должен оказаться на крыше строго раньше, чем полиция. Какое минимальное количество энергии ему придется потратить, чтобы этого добиться?

Входные данные

В первой строке дано одно целое число n (1 ≤ n ≤ 105).

В следующих n строках дано по два целых числа qi и ti (1 ≤ qi ≤ 109, 1 ≤ ti ≤ 3).

Выходные данные

Выведите одно целое число - минимальное количество энергии, которое придется потратить грабителю, чтобы безопасно добраться до крыши.

Замечание

На нулевом этаже грабитель обязан воспользоваться чипом, затратив пять единиц энергии. Через минуту, он будет на первом этаже, а его преследователи начнут движение. Тогда ещё через минуту они будут на втором этаже, где грабитель обязан воспользоваться чипом еще раз. На это он потратит ещё пять единиц энергии. Тогда через минуту он будет на крыше, и сможет безопасно покинуть здание. В итоге он потратит 5 + 5 = 10 единиц энергии.