항공권 묶음의 수하물 요금

문제

여행 준비를 맡은 담당자가 여러 사람의 항공권을 한 번에 결제하려고 한다. 결제할 항공권은 모두 N장이며, 각 항공권은 한 사람이 이용한다. 항공권마다 기본 운임과 이용자가 맡길 수하물의 무게가 정해져 있다. 담당자는 모든 항공권의 기본 운임과 수하물 추가 요금을 합친 최종 결제 금액을 구해야 한다. 각 항공권에는 F킬로그램까지의 수하물을 무료로 맡길 수 있는 혜택이 포함되어 있다. 수하물 무게가 F킬로그램 이하라면 추가 요금은 없다. F킬로그램을 넘으면 초과한 무게 1킬로그램마다 P원의 추가 요금을 낸다. 수하물 무게는 정수로 주어지므로 무게를 올림하거나 반올림할 필요는 없다. 기본 운임에는 이 추가 요금이 포함되어 있지 않다. 무료 수하물 혜택은 항공권마다 따로 적용한다. 어떤 이용자의 수하물이 무료 한도보다 가볍더라도 남은 한도를 다른 이용자에게 넘길 수 없다. 또한 여러 사람의 수하물 무게를 먼저 합친 뒤 무료 한도를 빼는 방식으로 계산하지 않는다. 각 항공권의 추가 요금을 개별적으로 구한 다음, 그 항공권의 기본 운임에 더해야 한다. 모든 항공권은 같은 무료 한도 F와 같은 추가 요금 P를 사용하지만, 기본 운임과 수하물 무게는 서로 다를 수 있다. 수하물을 맡기지 않는 이용자의 무게는 0으로 주어진다. 할인, 세금, 좌석 선택 요금 등 다른 금액은 없으며 입력에 주어진 규칙만 적용한다. N은 1 이상 1,000 이하의 정수다. 모든 항공권을 빠짐없이 결제할 때 필요한 총금액을 원 단위의 정수로 출력한다.

입력

첫째 줄에 항공권 수 N, 무료 수하물 한도 F, 초과 무게 1킬로그램당 요금 P가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ F ≤ 100, 1 ≤ P ≤ 10,000)
다음 N개 줄에 각 항공권의 기본 운임 B_i와 수하물 무게 W_i가 공백으로 구분되어 주어진다. (1 ≤ B_i ≤ 1,000,000, 0 ≤ W_i ≤ 100)
운임과 요금의 단위는 원이고, 무게의 단위는 킬로그램이다. 입력의 모든 수는 정수다.

출력

모든 항공권의 기본 운임과 수하물 추가 요금을 합친 총금액을 정수 하나로 출력한다.

3 12 700
40000 10
55000 15
30000 12

127100

2 0 900
10000 0
20000 4

33600

2 20 1000
15000 5
18000 20

33000

출처: Devin.KR 자체 제작