問題一覧 > 通常問題

No.2390 Udon Coupon (Hard)

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 71
作問者 : GlinTFraulein / テスター : cleantted tatyam PCTprobability Mizar 👑 amentorimaru
お気に入りにしたユーザー ProblemId : 9508 / 自分の提出
問題文最終更新日: 2023-07-20 05:48:51
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 398 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。