Вы играете в компьютерную игру, которая называется Splay the Sire. Сейчас Вы сражаетесь с финальным боссом игры.
Битва с боссом состоит из \(n\) ходов. В течение каждого хода Вы получаете некоторое количество карт. Каждая карта имеет два параметра: ее цену \(c_i\) и урон \(d_i\). Вы можете играть какими-то картами в какой-то последовательности в течение каждого хода (Вы выбираете карты и точный порядок, в котором их поставите) до тех пор, пока суммарная стоимость карт, которыми Вы играете в течение хода, не превосходит \(3\). После игры некоторым (возможно, нулевым) количеством карт Вы заканчиваете ход, а все карты, которыми Вы не сыграли, пропадают. Заметьте, что вы можете использовать каждую карту не более одного раза.
Ваш персонаж также нашел артефакт, который позволяет увеличить урон некоторых действий: каждая \(10\)-я карта, которую Вы играете, наносит двойной урон.
Чему равен максимально возможный урон, который Вы можете нанести в течение \(n\) ходов?
Выходные данные
Выведите одно целое число — максимально возможный урон, который Вы можете нанести.
Примечание
В тестовом примере лучшая последовательность действий будет выглядеть следующим образом:
В течение первого хода сыграть всеми тремя картами и нанести \(18\) единиц урона.
В течение второго хода сыграть обеими картами и нанести \(7\) единиц урона.
В течение третьего хода сыграть первой и третьей картами и нанести \(13\) единиц урона.
В течение четвертого хода сыграть первой и третьей картами и нанести \(25\) единиц урона.
В течение пятого хода сыграть единственной картой, которая нанесет двойной урон (\(200\)).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
1 6
1 7
1 5
2
1 4
1 3
3
1 10
3 5
2 3
3
1 15
2 4
1 10
1
1 100
|
263
|