Поликарп играет в компьютерную игру (да, опять). В этой игре он сражается с монстрами при помощи заклинаний.
Есть два типа заклинаний: огненный шар силы \(x\) наносит \(x\) урона монстру, а молния силы \(y\) наносит \(y\) урона монстру и удваивает урон следующего заклинания. Каждое заклинание может быть использовано только один раз, но Поликарп может применять их в любом порядке.
Например, предположим, что Поликарп знает три заклинания: огненный шар силы \(5\), молнию силы \(1\) и молнию силы \(8\). Всего есть \(6\) способов выбрать порядок заклинаний:
- первое, второе, третье. В таком случае вы нанесете \(5 + 1 + 2 \cdot 8 = 22\) урона;
- первое, третье, второе. В таком случае вы нанесете \(5 + 8 + 2 \cdot 1 = 15\) урона;
- второе, первое, третье. В таком случае вы нанесете \(1 + 2 \cdot 5 + 8 = 19\) урона;
- второе, третье, первое. В таком случае вы нанесете \(1 + 2 \cdot 8 + 2 \cdot 5 = 27\) урона;
- третье, первое, второе. В таком случае вы нанесете \(8 + 2 \cdot 5 + 1 = 19\) урона;
- третье, второе, первое. В таком случае вы нанесете \(8 + 2 \cdot 1 + 2 \cdot 5 = 20\) урона.
Изначально Поликарп знает \(0\) заклинаний. Его набор заклинаний меняется \(n\) раз, каждый раз он либо учит новое заклинание, либо забывает старое. После каждого изменения выведите максимально количество урона, которое можно нанести при помощи имеющихся заклинаний.
Выходные данные
После каждого изменения выведите максимально количество урона, которое можно нанести при помощи имеющихся заклинаний.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 5
0 10
1 -5
0 5
1 11
0 -10
|
5
25
10
15
36
21
|