問題一覧 > 通常問題

No.2390 Udon Coupon (Hard)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 65
作問者 : GlinTFrauleinGlinTFraulein / テスター : cleanttedcleantted 👑 tatyamtatyam 👑 PCTprobabilityPCTprobability 👑 MizarMizar 👑 amentorimaruamentorimaru
3 ProblemId : 9508 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-07-20 05:48:51

問題文

あるうどん屋では、「うどん札」をいくつか使うことで、割引を受けることができます。

割引の受け方は、以下の $3$ 種類です。

  • 「うどん札」を $A_1$ 枚使って、 $B_1$ 円の割引を受ける
  • 「うどん札」を $A_2$ 枚使って、 $B_2$ 円の割引を受ける
  • 「うどん札」を $A_3$ 枚使って、 $B_3$ 円の割引を受ける

これらの割引は、「うどん札」があれば何度でも受けられますが、使った「うどん札」は消費されます。

さて、みどりさんは「うどん札」を使って、できるだけたくさんの割引を受けたいと考えました。「うどん札」が $N$ 枚ある時、割引額の合計の最大値 $D$ を求めてください。

制約

  • $1\le N\le 10^{12}$
  • $1\le A_i\le 2000$
  • $1\le B_i\le 10^6$
  • 入力は全て整数

入力

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$A_3$ $B_3$

出力

$D$

割引額の合計の最大値 $D$ を整数で出力せよ。

サンプル

サンプル1
入力
16
3 90
5 100
10 390
出力
570
  • 「うどん札」を $3$ 枚使い、 $90$ 円の割引を受けます。
  • 「うどん札」を $3$ 枚使い、もう一度 $90$ 円の割引を受けます。
  • 「うどん札」を $10$ 枚使い、 $390$ 円の割引を受けます。

合計で割引額は $570$ 円です。これ以上の割引額を達成することはできません。

サンプル2
入力
50
80 800000
90 900000
100 1000000
出力
0

「うどん札」を全て消費することができない場合や、 $1$ 枚も使えない場合もあります。

サンプル3
入力
1000000000000
1300 800000
1700 900000
2000 1000000
出力
615384615200000

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。