問題一覧 > 通常問題

No.2701 A cans -> B cans

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 62
作問者 : Magentor / テスター : hamamu hirayuu_yc
0 ProblemId : 10272 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-29 21:52:24

問題文

p=1,2,…,Mp=1,2,\dots,M について、独立に以下の問題を解いてください。

Magentor君は、空き缶 00 を pp 個持っています。

また、NN 個の店があり、ii 番目の店では空き缶 00 または空き缶 ii を合計 AiA_i 個渡すと、 BiB_i 個のジュース入りの缶 ii と交換してもらうことができます。ここで、Ai>BiA_i>B_i が保証されます。

Magentor君は、11 個のジュース入りの缶 ii を、ジュースを飲むことで 11 個の空き缶 ii にすることができます。このとき、CiC_i の嬉しさを得ます。

Magentor君が得られる嬉しさの和の最大値を求めてください。

入力

N MN\ M
A1 B1 C1A_1\ B_1\ C_1
A2 B2 C2A_2\ B_2\ C_2
⋮\vdots
AN BN CNA_N\ B_N\ C_N
  • 1≤N≤50001\leq N\leq 5000
  • 2≤M≤50002\leq M\leq 5000
  • 1≤Bi<Ai≤M1\leq B_i<A_i\leq M
  • 1≤Ci≤1091\leq C_i\leq 10^9
  • 入力はすべて整数

出力

MM 行出力してください。

ii 行目には、p=ip=i としたときの答えを出力してください。

サンプル

サンプル1
入力
2 5
4 3 3
5 2 8
出力
0
0
0
9
18

p=5p=5 のとき、はじめMagentor君は空き缶 00 を 55 個持っています。以下のようにすることで、嬉しさの和を 1818 にすることができます。

  • 店 11 で、44 個の空き缶 00 を、33 個のジュース入りの缶 11 と交換する。
  • 33 個のジュース入りの缶 11 を、33 個の空き缶 11 にする。このとき、99 の嬉しさを得る。
  • 店 11 で、11 個の空き缶 00 と 33 個の空き缶 11 を、33 個のジュース入りの缶 11 と交換する。
  • 33 個のジュース入りの缶 11 を、33 個の空き缶 11 にする。このとき、99 の嬉しさを得る。

どのようにしても嬉しさの和を 1919 以上にはできないので、p=5p=5 のときは 1818 が答えです。

サンプル2
入力
1 2
2 1 1000000000
出力
0
1000000000
サンプル3
入力
3 10
9 8 1
5 1 8
5 2 4
出力
0
0
0
0
8
8
8
16
16
16

空き缶 11 を店 22 や店 33 で交換してもらうことはできないことに注意してください。

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