요금

시간 제한2초메모리 제한128 MB

요약

메시지당 기본요금과 가격 및 제공량이 고정된 두 종류의 문자 패키지가 주어질 때, T개의 문자를 보내는 최소 비용을 구합니다.

난이도: 어려움10점 중 8점
유형: 수학, 정수론, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

민식텔레콤은 이동통신 회사이다. 기본 요금제에서는 문자메시지 한 건당 10원을 낸다.

민식텔레콤은 문자팩도 판매한다. 문자팩을 구매하면 정해진 개수의 문자메시지를 기본 요금 없이 보낼 수 있다. 각 종류의 문자팩은 여러 번 구매할 수 있다. 한 달에 보낸 문자메시지 수가 구매한 문자팩들이 제공하는 총 개수를 넘으면, 초과한 문자메시지는 한 건당 10원의 기본 요금을 낸다.

영식이는 한 달 요금을 최소화하려고 한다. 영식이가 한 달에 보내는 문자메시지 수는 T개이다. 문자팩은 두 종류가 있다. 첫 번째 문자팩의 가격은 P1원이고 K1개의 문자메시지를 제공한다. 두 번째 문자팩의 가격은 P2원이고 K2개의 문자메시지를 제공한다. 두 종류의 문자팩을 함께 구매해도 되며, 구매한 문자팩들이 제공하는 문자메시지의 총량이 T보다 커도 된다.

입력

첫째 줄에 다섯 정수 T, K1, P1, K2, P2가 주어진다.

출력

가능한 월 요금의 최솟값을 출력한다.

제한

0 <= T <= 10^12
1 <= K1, K2 <= 10^12
1 <= P1, P2 <= 10^13
P1 <= 20 * K1
P2 <= 20 * K2

예제8

예제 1
입력
```
92 10 90 20 170
```
예상 출력
```
790
```
예제 2
입력
```
90 10 90 20 170
```
예상 출력
```
770
```
예제 3
입력
```
99 10 90 20 170
```
예상 출력
```
850
```
예제 4
입력
```
10 1 11 20 300
```
예상 출력
```
100
```
예제 5
입력
```
0 10 80 50 400
```
예상 출력
```
0
```
예제 6
입력
```
28 1 10 1 8
```
예상 출력
```
224
```

예제 7

입력

450702146848 63791 433956 115281 666125

예상 출력

2604279739220

예제 8
입력
```
45 6 12 7 14
```
예상 출력
```
90
```