Чтобы расслабиться перед участием в финале чемпионата мира ICPC, Вы решили поиграть в компьютерную игру под названием "Квесты". Вы уже играли в нее несколько раз и теперь хотите добиться идеального прохождения — чтобы подготовиться к идеальному прохождению финала!
В игре необходимо выполнить ряд квестов, и за выполнение каждого из них Вы зарабатываете очки опыта (XP). Общее количество очков опыта, заработанных Вами в любой момент времени, определяет Ваш текущий уровень. Вы достигаете нового уровня за каждые заработанные v XP. Формально Ваш уровень в любой момент времени — это наибольшее целое число l, при котором у вас есть как минимум l⋅v опыта.
Каждому квесту присваивается количество x опыта и целевой уровень сложности d. Если Вы завершаете квест с уровнем не ниже d, то заработаете x опыта. Однако, если Вы завершите квест с уровнем меньше d, то заработаете c⋅x XP. Константа c — это множитель опыта, который дает бонус за выполнение квеста, когда Ваш уровень ниже рекомендуемого уровня d.
Вы знаете все n квестов и соответствующие им значения x и d (Вы также знаете числа v и c — Вы много играли в эту игру). Вы также достаточно опытны, чтобы выполнить любой квест, независимо от его целевого уровня сложности и вашего уровня. Вы хотите выполнить все квесты в таком порядке, который позволит вам заработать как можно больше опыта.
Во входном примере максимальное количество опыта, которое Вы можете заработать, составляет 43, что делается следующим образом. Сначала завершите второй квест (заработаете 4 опыта, поскольку находитесь на уровне 0 и выполнили квест с целевым уровнем сложности 2). Затем завершите первый квест (заработаете 30 опыта, поскольку все еще находитесь на уровне 0, а целевой уровень сложности составляет 1). Имея 34 опыта, Вы теперь достигли уровня 3. Наконец, завершите третий квест (за который заработаете 9 опыта без множителя, поскольку уже находитесь на уровне 3).
В первой строке заданы три целых числа n,v и c, где n (1≤n≤2000) — количество квестов в игре, v (1≤v≤2000) — это количество опыта, необходимое для достижения каждого уровня, а c (2≤c≤2000) — множитель опыта за выполнение квеста до достижения целевого уровня сложности.
Далее следуют n строк, каждая из которых содержит два целых числа x и d, описывающие один квест, где x (1≤x≤2000) — количество очков опыта, которые Вы зарабатываете за выполнение этого квеста если находитесь на целевом уровне сложности или выше, а d (1≤di≤106) — целевой уровень сложности для этого квеста.
Выведите максимально возможное количество очков опыта, которое Вы сможете заработать, выполнив все квесты.