Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

E. Неплохо сыграно!
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно Максим увлекся известной ККИ «BrainStone». Так как «BrainStone» весьма интеллектуальная игра, в её процессе Максиму постоянно приходится решать сложные задачи. Вот одна из них:

Всего у Максима n существ, i-е характеризуется двумя числами – своим здоровьем hpi и своим уроном dmgi. Также у Максима есть в запасе заклинания двух типов:

  1. Удваивает здоровье существа (hpi := hpi·2);
  2. Приравнивает урон существа к его здоровью (dmgi := hpi).

Заклинание первого типа можно использовать не более a раз суммарно, второго не более b раз суммарно. Заклинание может быть использовано на одном существе несколько раз. Заклинания можно использовать в любом порядке. Также не обязательно использовать все заклинания.

Так как Максим слишком занят подготовкой к сессии, он просит вас посчитать, какой максимальный суммарный урон существ можно получить, если оптимально применять заклинания.

Входные данные

Первая строка содержит три целых числа n, a, b (1 ≤ n ≤ 2·105, 0 ≤ a ≤ 20, 0 ≤ b ≤ 2·105) — количество существ, заклинаний первого и второго типа соответственно.

i-я из следующих n строк содержат два числа hpi и dmgi (1 ≤ hpi, dmgi ≤ 109) — характеристики i-го существа.

Выходные данные

В единственной строке выведите одно число — максимальный урон, который могут нанести существа.

Примеры
Входные данные
2 1 1
10 15
6 1
Выходные данные
27
Входные данные
3 0 3
10 8
7 11
5 2
Выходные данные
26
Примечание

В первом примере Максиму нужно использовать заклинание первого типа на второе существо, а затем заклинание второго типа на него же. Тогда суммарный урон существ будет равен 15 + 6·2 = 27.

Во втором примере Максиму нужно использовать заклинание второго типа на первое существо и заклинание второго типа на третье существо. Суммарный урон существ получится 10 + 11 + 5 = 26.