14628번 - 입 챌린저

광현이는 자칭 게임 아티스트이다. 게임 아티스트라고 해서 게임 캐릭터를 디자인하는 일이 아니라 게임을 Art하게 플레이하는 것을 의미한다. 광현이는 요즘 '리그오브스톰'이라는 게임에 빠졌다. 리그오브스톰은 스킬을 써서 상대방의 체력을 0 이하로 만들면 이기는 게임이다. 스킬은 총 N개가 있는데, 모든 스킬에는 사용 시 마나 포인트라는 비용이 필요하다. 또한, 스킬마다 상대방의 체력을 깎을 수 있는 수치가 정해져 있다. 스킬 사용 제한 횟수는 없지만 같은 스킬을 한 번 이상 사용할 때엔 필요한 마나 포인트가 원래 마나 포인트에서 K씩 추가로 증가한다. 예를 들어 어떤 스킬의 마나 포인트가 10이고 K값이 5이면 처음 사용할 때는 10, 그다음은 15, 그다음은 20 이런 식으로 증가하게 된다. 광현이는 이 게임을 아주 많이 플레이하여 브론즈 등급에 있었지만 슬슬 질려가고 있었다. 그래서 광현이는 게임 아티스트답게 플레이에 어떤 제약을 걸고 게임에 임하려고 한다. 그 제약이란 상대방의 체력을 정확하게 0으로 만들면서 마나 포인트를 최대한 적게 사용하는 것이다. 과연 광현이는 이 제약을 지킬 수 있을까? 광현이의 플레이가 맞는지 확인하기 위해 적의 체력을 정확하게 0으로 만들 때 필요한 가장 적은 마나 포인트를 구해보자.

입력은 항상 적의 체력을 정확히 0으로 만들 수 있는 스킬의 조합만 들어온다. 첫째 줄에 스킬의 개수 N, 적의 체력 M, 같은 스킬을 사용할 때마다 추가되는 마나 포인트 K가 주어진다. (1≤N,M,K≤100) 둘째 줄부터 N개의 줄에 걸쳐서 한 줄마다 스킬에 필요한 마나 포인트 X와 상대방의 체력을 깎는 수치인 Y가 주어진다. (1≤X,Y≤100)

첫째 줄에 적의 체력을 정확하게 0 으로 만들 때 필요한 가장 적은 마나 포인트를 출력한다.