Квести

Щоб розслабитися перед фіналом чемпіонату світу ICPC, ви вирішили пограти в комп'ютерну гру під назвою "Квести". Ви вже неодноразово грали в цю гру і тепер прагнете досягти ідеального проходження — щоб підготуватися до ідеального виступу у фіналі!

У грі потрібно виконати ряд квестів, за кожен з яких ви отримуєте очки досвіду (XP). Загальна кількість зароблених очок досвіду визначає ваш поточний рівень. Ви підвищуєте рівень за кожні $v$ зароблених XP. Формально, ваш рівень у будь-який момент часу — це найбільше ціле число $l$, для якого у вас є принаймні $l\cdot v$ досвіду.

Кожен квест має певну кількість $x$ досвіду і цільовий рівень складності $d$. Якщо ви завершуєте квест на рівні, не нижчому за $d$, то отримуєте $x$ досвіду. Якщо ж ваш рівень нижчий за $d$, то ви заробите $c\cdot 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\le n\le 2000)$ — кількість квестів у грі, $v(1\le v\le 2000)$ — кількість досвіду, необхідна для досягнення кожного рівня, а $c(2\le c\le 2000)$ — множник досвіду за виконання квесту до досягнення цільового рівня складності.

Далі йдуть $n$ рядків, кожен з яких містить два цілі числа $x$ і $d$, що описують один квест, де $x(1\le x\le 2000)$ — кількість очок досвіду, які ви отримуєте за виконання цього квесту, якщо ваш рівень відповідає цільовому або вищий, а $d(1\le d_i\le 10^6)$ — цільовий рівень складності для цього квесту.

Вихідні дані

Виведіть максимально можливу кількість очок досвіду, яку ви зможете заробити, виконавши всі квести.

Приклади