← 返回题目列表

AtCoder · yahoo_procon2017_qual_d

D. 工场

中文机器翻译题面 查看原题

配点 : 1000 点

問題文

高桥君是工厂的经营者。 现在正在休假,工厂里没有商品, 1 休假结束后, 1 第几天起每天计划生产 K 个商品。

此外,这家工厂非常受欢迎,有时会接到订单。 但是,这家工厂接到的订单稍微有些特殊,采用以下形式进行。

  • 注文 (D,A) : 从休假结束后的 D 第几天起,商品生产完成后,最多可以 A 个被购买。实际卖出的数量可以由高桥君在 0~A 个范围内选择。但是,不能超过库存数量。

作为这家工厂的编程负责人,你会收到高桥君关于新增订单或财务问题的 Q 信息。 i 第几条信息将以以下形式输入。

  • 注文追加「1\ D_i\ A_i」: (D_i,A_i) 这种形式的订单会被添加到工厂。
  • 経理質問「2\ D_i」: 到提问时为止收到的订单为准,休假结束后的 D_i 天内完成商品生产和订单处理时,最多可以销售多少商品。

请正确回答所有财务问题,帮助高桥君管理经营。

制約

  • 1 ≦ Q ≦ 10^5
  • 1 ≦ K ≦ 10^9
  • 1 ≦ D_i≦ 10^9
  • 1 ≦ A_i≦ 10^9

部分点

  • 600 在小部分测试用例中,财务问题中的 D_i 值总是 10^9 。

入力

输入是按以下格式从标准输入给出的。

Q K
Information_1
Information_2
:
Information_Q

出力

财务问题的答案,按问题给出的顺序分别 1 逐行输出。


入力例 1

5 2
1 3 5
2 1
1 1 3
2 1
2 3

出力例 1

0
2
6

例如,在最后一个财务问题时的最佳商品销售方式如下。

  • 休假结束后的 1 天生产商品 2 个,然后销售商品 1 个。这时,商品剩余 1 个。
  • 休假结束后的 2 天生产商品 2 个生产。这时,商品是 3 个。
  • 休假结束后的 3 天生产商品 2 个,然后销售商品 5 个卖出。

入力例 2

4 2
1 5 5
2 1000000000
1 2 7
2 1000000000

出力例 2

5
9

此输入满足部分得分的限制。


入力例 3

10 4
2 6
1 5 7
2 6
2 4
2 1
2 7
1 5 7
2 7
2 2
1 4 6

出力例 3

0
7
0
0
7
14
0