No.2390 Udon Coupon (Hard)
タグ : / 解いたユーザー数 71
作問者 :
GlinTFraulein
/ テスター :
cleantted
tatyam
PCTprobability
amentorimaru
Problem Statement
At a certain udon restaurant, you can receive discounts by using some "udon coupons".
There are the following $3$ ways to receive a discount.
- Use $A_1$ "udon coupons" to receive a discount of $B_1$ yen
- Use $A_2$ "udon coupons" to receive a discount of $B_2$ yen
- Use $A_3$ "udon coupons" to receive a discount of $B_3$ yen
These discounts can be received any number of times as long as you have "udon coupons", but the "udon coupons" used are consumed.
Now, Midori wants to receive as large a discount as possible using her "udon coupons". When she has $N$ "udon coupons", find the maximum total discount amount $D$.
Constraints
- $1\le N\le 10^{12}$
- $1\le A_i\le 2000$
- $1\le B_i\le 10^6$
- All inputs are integers
Input
$N$ $A_1$ $B_1$ $A_2$ $B_2$ $A_3$ $B_3$
Output
$D$
Output the maximum total discount amount $D$ as an integer.
Sample
Sample 1
Input
16 3 90 5 100 10 390
Output
570
- Use $3$ "udon coupons" to receive a discount of $90$ yen.
- Use $3$ "udon coupons" to receive a discount of $90$ yen once more.
- Use $10$ "udon coupons" to receive a discount of $390$ yen.
The total discount is $570$ yen. No larger discount can be achieved.
Sample 2
Input
50 80 800000 90 900000 100 1000000
Output
0
There may be cases where not all of the "udon coupons" can be consumed, or where not even $1$ of them can be used.
Sample 3
Input
1000000000000 1300 800000 1700 900000 2000 1000000
Output
615384615200000
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。