최소 마나로 체력 0 만들기

광현이는 '리그오브스톰'이라는 게임을 한다. 스킬을 써서 상대의 체력을 0 이하로 만들면 이기는 게임이지만, 광현이는 스스로 제약을 걸었다. 상대의 체력을 정확히 0으로 만들면서 마나 포인트를 가장 적게 쓰는 것이다.

스킬은 모두 $N$개다. $i$번 스킬을 한 번 쓰면 마나 포인트 $X_i$를 소모하고 상대의 체력을 $Y_i$만큼 깎는다. 사용 횟수에는 제한이 없지만, 같은 스킬을 다시 쓸 때마다 그 스킬의 소모량이 $K$씩 늘어난다. 예를 들어 마나 포인트가 10이고 $K$가 5인 스킬은 첫 번째 사용에 10, 두 번째 사용에 15, 세 번째 사용에 20을 소모한다. 증가량은 스킬마다 따로 계산하고, 스킬을 쓰는 순서는 전체 소모량을 바꾸지 않는다.

상대의 체력이 $M$일 때, 체력을 정확히 0으로 만드는 데 필요한 최소 마나 포인트를 구하자.

첫째 줄에 스킬의 개수 $N$, 적의 체력 $M$, 같은 스킬을 다시 쓸 때마다 늘어나는 마나 포인트 $K$가 주어진다. ($1 \le N, M, K \le 100$)

둘째 줄부터 $N$개의 줄에 스킬 하나의 정보가 주어진다. 각 줄에는 그 스킬에 필요한 마나 포인트 $X$와 깎는 체력 $Y$가 주어진다. ($1 \le X, Y \le 100$)

적의 체력을 정확히 0으로 만드는 조합이 존재하는 입력만 주어진다.

첫째 줄에 적의 체력을 정확히 0으로 만들 때 필요한 최소 마나 포인트를 출력한다.