U, Our Star!

면접 대비

시간 제한1초메모리 제한1024 MB

요약

상품의 수량과 가격이 주어질 때, 포인트를 최대로 받는 최소 결제 금액을 구합니다. 포인트는 결제액을 X로 나눈 몫에 Y를 곱한 값이며 D를 넘지 않습니다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

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

카페에서는 다음 행사를 진행한다.

카페에서 $X$ 원을 쓸 때마다 U, Our Star! 적립금을 $Y$ 만큼 지급한다.
받을 수 있는 최대 U, Our Star! 적립금은 $D$ 이다.

귀여운 이루매 굿즈를 굉장히 좋아하는 알림이는 이 기회에 U, Our Star! 적립금을 최대한 많이 모으려고 한다. 알림이는 가진 돈이 충분히 많아서 상품을 원하는 대로 구입할 수 있다. 하지만 과소비는 싫어서, 적립금을 최대화하는 지불 금액 중 가장 적은 금액을 내고 싶다.

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

입력

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

$1 \le Y < X \le 100000$
$D$ 는 $Y$ 의 양의 정수배이며, $D \div Y \times X \le 100000$ 을 만족한다.

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

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

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

출력

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

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

예제2

예제 1
입력
```
10 1 5
2
1 5
4 10
```
예상 출력
```
40
```
예제 2
입력
```
10 1 5
4
1 5
4 10
1 11
1 12
```
예상 출력
```
51
```