No.3509 Get More Money
タグ : / 解いたユーザー数 15
作問者 :
Naru820
/ テスター :
Nzt3
rhoo
Solalyth
問題文
商人のAliceは今から $N$ 日間かけてゴールドを稼ぐことにしました。Aliceははじめ $10^{100}$ ゴールド持っており、ジュエルは $1$ つも持っていません。
Aliceは $i$ 日目に以下の2種類の取引を行えます。
- $A_i$ ゴールド払って、ジュエルを $1$ つ買う。この取引は最大で $B_i$ 回まで行える。
- ジュエルを $1$ つ売って、$C_i$ ゴールドを得る。この取引はジュエルを $1$ つ以上持っているときのみ行え、最大で $D_i$ 回まで行える。
また、Aliceの家には保管庫があり、最大で $K$ 個までジュエルを保管することができます。Aliceはジュエルを保管庫に入れないと翌日には失くしてしまいますが、保管庫に入れれば失くさず、翌日以降保管しておいたジュエルを使って取引することが出来ます。
$N$ 日間の取引で、Aliceは最大でゴールドをいくら稼ぐことができますか？
より正確には、$N$ 日目の取引を終えた後の、Aliceが持っているゴールドとして考えられる最大値を $S$ ゴールドとして、 $S - 10^{100}$ を求めてください。
テストケースは全部で $T$ ケースあります。
制約
- $1 \leq T \leq 2 \times 10^5$
- $1 \leq N \leq 2 \times 10^5$
- $1 \le K \le 10^{12}$
- $1 \le A_i,B_i,C_i,D_i \le 5 \times 10^6$
- すべてのテストケースに対する $N$ の総和は $2\times 10^5$ 以下
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。ここで、 $\text{case}_i$ は $i$ 番目のテストケースです。
$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_{T}$
各テストケースは以下の形式で与えられます。
$N\ K$ $A_1 \ A_2 \ldots A_N$ $B_1 \ B_2 \ldots B_N$ $C_1 \ C_2 \ldots C_N$ $D_1 \ D_2 \ldots D_N$
出力
$T$ 行出力してください。 $i$ 行目には、 $\text{case}_i$ に対する答えを出力してください。
サンプル
サンプル1
入力
3 3 2 1 3 2 3 3 1 2 1 3 1 3 2 4 1 4 2 1 3 5 6 2 3 7 3 1 9 5 1 4 8 13 4929798 1150434 88899 539811 1769519 4292449 4934296 4400709 64937 1760077 744701 456322 3779656 921043 1887669 2018657 3548740 193710 2991728 1964569 480243 2058687 4154332 3477027 3826799 1745255 2251591 3069743 1945307 3516424 4440181 1139192 489673 3089401 891641 1437747 2861899 984159 3969672 1605868 4638874 260809 499501 4269856 2551383 194827 2822117 1338907 2315113 866580 180577 1820692 1137521
出力
5 42 37267031954271
1つ目のテストケースについて、以下のように取引を行うことで、Aliceは $5$ ゴールド稼ぐことが出来ます。
- 1日目 $3$ ゴールド払って、ジュエルを $3$ 個買う。そのあと、$1$ つジュエルを売って、 $2$ ゴールドを得る。そして、保管庫に $2$ 個ジュエルを入れる。
- 2日目 何もしない。
- 3日目 保管庫からジュエルを $2$ 個取り出す。 $2$ つジュエルを売って、$6$ ゴールドを得る。
また、どのように取引を行っても、 $6$ ゴールド以上稼ぐことが出来ないことが証明できます。よって、$5$ を出力してください。
2つ目のテストケースについても、以下のように取引を行えば $42$ ゴールド稼ぐことが出来ます。
- 1日目 $20$ ゴールド払って、ジュエルを $5$ 個買う。そのあと、$5$ つジュエルを売って、 $35$ ゴールドを得る。
- 2日目 $2$ ゴールド払って、ジュエルを $1$ 個買う。そのあと、$1$ つジュエルを売って、$3$ ゴールドを得る。
- 3日目 $1$ ゴールド払って、ジュエルを $1$ つ買い、保管庫に入れる。
- 4日目 $9$ ゴールド払って、ジュエルを $3$ つ買う。そのあと、保管庫からジュエルを $1$ つ取り出し、ジュエルを $4$ つ売って、 $36$ ゴールドを得る。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。