Чтобы расслабиться перед участием в финале чемпионата мира ICPC, Вы решили поиграть в компьютерную игру под названием "Квесты". Вы уже играли в нее несколько раз и теперь хотите добиться идеального прохождения — чтобы подготовиться к идеальному прохождению финала!
В игре необходимо выполнить ряд квестов, и за выполнение каждого из них Вы зарабатываете очки опыта (XP). Общее количество очков опыта, заработанных Вами в любой момент времени, определяет Ваш текущий уровень. Вы достигаете нового уровня за каждые заработанные XP. Формально Ваш уровень в любой момент времени — это наибольшее целое число , при котором у вас есть как минимум опыта.
Каждому квесту присваивается количество опыта и целевой уровень сложности . Если Вы завершаете квест с уровнем не ниже , то заработаете опыта. Однако, если Вы завершите квест с уровнем меньше , то заработаете XP. Константа — это множитель опыта, который дает бонус за выполнение квеста, когда Ваш уровень ниже рекомендуемого уровня .
Вы знаете все квестов и соответствующие им значения и (Вы также знаете числа и — Вы много играли в эту игру). Вы также достаточно опытны, чтобы выполнить любой квест, независимо от его целевого уровня сложности и вашего уровня. Вы хотите выполнить все квесты в таком порядке, который позволит вам заработать как можно больше опыта.
Во входном примере максимальное количество опыта, которое Вы можете заработать, составляет , что делается следующим образом. Сначала завершите второй квест (заработаете опыта, поскольку находитесь на уровне и выполнили квест с целевым уровнем сложности ). Затем завершите первый квест (заработаете опыта, поскольку все еще находитесь на уровне , а целевой уровень сложности составляет ). Имея опыта, Вы теперь достигли уровня . Наконец, завершите третий квест (за который заработаете опыта без множителя, поскольку уже находитесь на уровне ).
В первой строке заданы три целых числа и , где — количество квестов в игре, — это количество опыта, необходимое для достижения каждого уровня, а — множитель опыта за выполнение квеста до достижения целевого уровня сложности.
Далее следуют строк, каждая из которых содержит два целых числа и , описывающие один квест, где — количество очков опыта, которые Вы зарабатываете за выполнение этого квеста если находитесь на целевом уровне сложности или выше, а — целевой уровень сложности для этого квеста.
Выведите максимально возможное количество очков опыта, которое Вы сможете заработать, выполнив все квесты.