Поликарп играет в компьютерную игру (да, опять). В этой игре он сражается с монстрами при помощи заклинаний.

Есть два типа заклинаний: огненный шар силы $$$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$$$ раз, каждый раз он либо учит новое заклинание, либо забывает старое. После каждого изменения выведите максимально количество урона, которое можно нанести при помощи имеющихся заклинаний.