Недавно Максим увлекся известной ККИ «BrainStone». Так как «BrainStone» весьма интеллектуальная игра, в её процессе Максиму постоянно приходится решать сложные задачи. Вот одна из них:
Всего у Максима n существ, i-е характеризуется двумя числами – своим здоровьем hpi и своим уроном dmgi. Также у Максима есть в запасе заклинания двух типов:
- Удваивает здоровье существа (hpi := hpi·2);
- Приравнивает урон существа к его здоровью (dmgi := hpi).
Заклинание первого типа можно использовать не более a раз суммарно, второго не более b раз суммарно. Заклинание может быть использовано на одном существе несколько раз. Заклинания можно использовать в любом порядке. Также не обязательно использовать все заклинания.
Так как Максим слишком занят подготовкой к сессии, он просит вас посчитать, какой максимальный суммарный урон существ можно получить, если оптимально применять заклинания.
Выходные данные
В единственной строке выведите одно число — максимальный урон, который могут нанести существа.
Примечание
В первом примере Максиму нужно использовать заклинание первого типа на второе существо, а затем заклинание второго типа на него же. Тогда суммарный урон существ будет равен 15 + 6·2 = 27.
Во втором примере Максиму нужно использовать заклинание второго типа на первое существо и заклинание второго типа на третье существо. Суммарный урон существ получится 10 + 11 + 5 = 26.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1 1
10 15
6 1
|
27
|
|
2
|
3 0 3
10 8
7 11
5 2
|
26
|