Втеча з будівлі

Не все спокійно в Найт-Сіті. Грабіжник пограбував банк, розташований у n-поверховій будівлі, і тепер намагається втекти за допомогою гелікоптера на даху. Поверхи в будівлі пронумеровані від 0 до n - 1, а дах вважається поверхом номер n. Зараз правоохоронці знаходяться на нульовому поверсі разом із грабіжником.

У грабіжника є спеціальний чип, який дозволяє йому вимикати поліцейських роботів, коли грабіжник і поліція опиняються одночасно на одному поверсі. Ефективність чипа залежить від електричних полів поверху, на якому він був використаний. Зокрема, якщо, перебуваючи на i-му поверсі, грабіжник використав чип k разів (k — ціле додатне число), то на це витратиться k * q[i] одиниць енергії, а поліція буде зупинена на k * t[i] хвилин, і тільки після цього продовжить рух.

Грабіжник піднімається зі швидкістю один поверх за хвилину, а його переслідувачі піднімаються зі швидкістю два поверхи за хвилину. Кожного разу, коли поліція і грабіжник опиняються одночасно на одному поверсі, грабіжник зобов'язаний використати чип хоча б один раз, інакше поліція його схопить. Якщо поліція наздожене грабіжника між поверхами, він не зможе скористатися чипом і буде схоплений.

Щоб безпечно покинути будівлю, грабіжник повинен опинитися на даху строго раніше, ніж поліція. Яку мінімальну кількість енергії йому доведеться витратити, щоб цього досягти?

Вхідні дані

У першому рядку дано одне ціле число n (1 ≤ n ≤ 10^5).

У наступних n рядках дано по два цілі числа q[i] і t[i] (1 ≤ q[i] ≤ 10^9, 1 ≤ t[i] ≤ 3).

Вихідні дані

Виведіть одне ціле число — мінімальну кількість енергії, яку доведеться витратити грабіжнику, щоб безпечно дістатися до даху.

Примітка

На нульовому поверсі грабіжник зобов'язаний скористатися чипом, витративши п'ять одиниць енергії. Через хвилину він буде на першому поверсі, а його переслідувачі почнуть рух. Тоді ще через хвилину вони будуть на другому поверсі, де грабіжник зобов'язаний скористатися чипом ще раз. На це він витратить ще п'ять одиниць енергії. Тоді через хвилину він буде на даху і зможе безпечно покинути будівлю. В результаті він витратить 5 + 5 = 10 одиниць енергії.