항공권 묶음의 쿠폰 배정

문제

항공권 예약 서비스의 백엔드는 한 번에 결제할 항공권 묶음에 할인 쿠폰을 배정한다. 묶음에는 N장의 항공권이 있고, 사용할 수 있는 동일한 쿠폰은 K장이다. 각 항공권에는 기본 운임과 세율이 따로 정해져 있다. 서비스는 고객이 지불할 최종 합계가 가장 작아지도록 쿠폰을 배정해야 한다. 쿠폰 한 장은 항공권 한 장의 기본 운임을 D원 낮춘다. 한 항공권에는 쿠폰을 최대 한 장만 사용할 수 있으며, 사용한 쿠폰을 다른 항공권에 다시 사용할 수 없다. 기본 운임이 D원보다 작으면 할인 후 운임은 0원이다. 쿠폰을 사용하지 않은 항공권의 운임은 원래 기본 운임과 같다. 쿠폰은 최대 K장까지 사용할 수 있고, 남은 쿠폰을 반드시 사용할 필요는 없다. 세금은 쿠폰 적용 여부가 결정된 뒤 각 항공권에 대해 따로 계산한다. 할인 후 운임을 B원, 해당 항공권의 세율을 R퍼센트라고 하면 세금은 B × R ÷ 100을 원 단위로 올림한 정수다. 계산값이 이미 정수이면 그대로 사용하며, B가 0이면 세금도 0원이다. 해당 항공권의 최종 금액은 할인 후 운임과 이 세금의 합이다. 모든 항공권의 최종 금액을 더한 값이 결제 합계다. 항공권마다 세율이 다를 수 있으므로 쿠폰으로 줄어드는 최종 금액도 다를 수 있다. 세금의 올림은 항공권마다 수행하며, 여러 항공권의 운임을 합친 뒤 세금을 계산하지 않는다. 쿠폰 배정 방법이 여러 개여도 최소 결제 합계만 출력하므로 배정 순서나 동점인 항공권의 선택 순서는 결과에 영향을 주지 않는다. 쿠폰이 없으면 모든 항공권을 할인 없이 계산한다. 가능한 최소 결제 합계를 구한다.

입력

첫째 줄에 정수 N, K, D가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 20,000, 0 ≤ K ≤ N, 1 ≤ D ≤ 1,000,000,000이다.
다음 N개 줄에는 항공권의 기본 운임 P_i와 세율 R_i가 주어진다. P_i는 1 이상 1,000,000,000 이하의 정수이고, R_i는 0 이상 30 이하의 정수다. 모든 금액의 단위는 원이다.

출력

가능한 최소 결제 합계를 원 단위 정수로 한 줄에 출력한다. 천 단위 구분 기호나 소수점은 출력하지 않는다.

3 1 100
500 0
450 20
80 30

1024

2 0 50
101 3
200 0

305

3 2 10
3 30
10 0
11 10

6

출처: Devin.KR 자체 제작