32937번 - U, Our Star!

문제

서울시립대학교 카페는 오직 U, Our Star! 적립금으로만 구매할 수 있는 다양한 이루매 굿즈들을 판매하고 있다.

서울시립대학교 카페에서 진행하는 행사의 내용은 다음과 같다.

• 카페에서 사용한 돈 $X$원 당 $Y$만큼의 U, Our Star! 적립금을 지급한다.
• 최대로 받을 수 있는 U, Our Star! 적립금은 $D$이다.

귀여운 이루매 굿즈들을 굉장히 좋아하는 알림이는 이 기회에 최대한 많은 U, Our Star! 적립금을 모으고자 한다.

알림이는 갖고 있는 돈이 충분히 많아서, 카페의 상품을 원하는 대로 구입할 수 있다. 하지만 과소비는 싫기 때문에, 적립금을 최대화하는 비용 중 가장 적은 비용을 지불하고 싶다.

카페의 상품 정보가 구매 가능한 수량, 가격의 형태로 주어졌을 때, 받을 수 있는 U, Our Star! 적립금을 최대화하는 지불 금액 중 최소 지불 금액을 구하라.

입력

첫 번째 줄에 세 양의 정수 $X, \ Y, \ D$가 주어진다.

• 1ドル \le Y \lt X \le 100 \ 000$
• $D$는 $Y$의 양의 정수배이며, $D \div Y \times X \le 100 \ 000$를 만족한다.

두 번째 줄에 상품 정보의 수 $N$이 주어진다. (1ドル \le N \le 100$)

다음 줄부터 $N$개의 줄에 걸쳐 각 상품의 구매 가능한 수량 $a,ドル 상품 가격 $b$가 공백으로 구분되어 주어진다. (1ドル \le a \le 100,ドル 1ドル \le b \le 100 \ 000$)

모든 상품들의 구매 가능한 수량의 총합은 1ドル$이상 100ドル$이하이다.

출력

받을 수 있는 U, Our Star! 적립금을 최대화하는 지불 금액 중 최소 지불 금액을 출력하라.

단, 모든 상품들을 구매하더라도 U, Our Star! 적립금을 하나도 받을 수 없다면 0ドル$을 출력하라.

제한

힌트