Text Message Fees

Time limit2sMemory limit128 MB

Summary

Given a per-message fee and two reusable text-message packs with fixed price and quota, find the minimum cost to send exactly T messages.

Level: Hard8 of 10
Topics: Math, Number theory, Greedy, Implementation
Solved: No attempts yet

Problem

Minsik Telecom is a mobile carrier. Under its basic plan, each text message costs 10 won.

The company also sells text-message packs. When a customer buys a pack, they may send a fixed number of text messages without paying the basic per-message fee for those messages. Each kind of pack may be bought any number of times. If the customer sends more messages than the total number covered by purchased packs, every uncovered message is charged at the basic rate.

Youngsik wants to minimize his monthly bill. He sends T text messages in one month. There are two kinds of text-message packs. The first pack costs P1 won and covers K1 messages. The second pack costs P2 won and covers K2 messages. He may buy both kinds of packs, and the total number of messages covered by purchased packs may exceed T.

Input

The first line contains five integers T, K1, P1, K2, and P2.

Output

Output the minimum possible monthly fee.

Constraints

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

Examples8

Example 1
Input
```
92 10 90 20 170
```
Expected output
```
790
```
Example 2
Input
```
90 10 90 20 170
```
Expected output
```
770
```
Example 3
Input
```
99 10 90 20 170
```
Expected output
```
850
```
Example 4
Input
```
10 1 11 20 300
```
Expected output
```
100
```
Example 5
Input
```
0 10 80 50 400
```
Expected output
```
0
```
Example 6
Input
```
28 1 10 1 8
```
Expected output
```
224
```

Example 7

Input

450702146848 63791 433956 115281 666125

Expected output

2604279739220

Example 8
Input
```
45 6 12 7 14
```
Expected output
```
90
```