Вася играет в Geometry Horse.
Цель игры — уничтожить геометрические фигуры, находящиеся в игровом мире. За уничтожение фигуры начисляется определенное число очков в зависимости от типа фигуры и текущего множителя.
В данной игре имеется n видов геометрических фигур, для каждого вида известно количество фигур данного вида ki и стоимость одной фигуры данного вида ci. За уничтожение одной фигуры вида i игроку начисляется ci·f очков, где f — текущий множитель. Множитель может принимать целые значения от 1 до t + 1 включительно. Изначально множитель равен 1. После уничтожения pi (1 ≤ i ≤ t) фигур множитель становится равен i + 1, таким образом, фигура, уничтоженная по счету ровно (pi + 1)-ой, учитывается уже со множителем i + 1.
Ваша задача — определить, какое наибольшее число очков может набрать Вася, уничтожив все фигуры. Учтите, что Вася настолько силен, что может уничтожать фигуры в любом выбранном им порядке.
Выходные данные
Выведите единственное число — наибольшее количество очков, которое может набрать Вася.
Примечание
В первом примере Вася сначала уничтожит три фигуры и получит 3·1·10 = 30 очков. Затем множитель станет равным 2 и Вася, уничтожив оставшиеся две фигуры, получит еще 2·2·10 = 40 очков. Всего Вася получит 70 очков.
Во втором примере все 8 фигур будут уничтожены с коэффициентом 1, поэтому всего Вася наберет (3·8 + 5·10)·1 = 74 очка.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
5 10
2
3 6
|
70
|
|
2
|
2
3 8
5 10
1
20
|
74
|