Zero health with minimum mana

Gwanghyeon plays a game called League of Storms. You win by using skills to drop the opponent's health to 0 or below, but Gwanghyeon set his own restriction: bring the health to exactly 0 while spending as little mana as possible.

There are $N$ skills. Using skill $i$ once spends $X_i$ mana and removes $Y_i$ health from the opponent. A skill can be used any number of times, but every repeat of the same skill costs $K$ more mana than the previous use of that skill. For example, a skill with a cost of 10 and $K = 5$ spends 10 on the first use, 15 on the second, and 20 on the third. The increase is counted separately for each skill, and the order of the uses does not change the total.

The opponent's health is $M$. Find the smallest amount of mana needed to bring it to exactly 0.

The first line contains the number of skills $N$, the enemy's health $M$, and the extra mana $K$ added on each repeat of the same skill. ($1 \le N, M, K \le 100$)

Each of the next $N$ lines describes one skill with the mana it needs, $X$, and the health it removes, $Y$. ($1 \le X, Y \le 100$)

Every input has at least one combination that brings the enemy's health to exactly 0.

Print on the first line the smallest amount of mana needed to bring the enemy's health to exactly 0.