← 返回题目列表

AtCoder · jsc2022_final_e

E. 圆形寿司

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

配点 : 900 点

問題文

长度 周长为 2^L 。 距圆周上一点的距离 x 顺时针移动的点给出坐标 我们将其称为 x 点。

在圆周上 N 寿司在动。 i 第一个寿司是时候了 坐标为 0 坐标到 A_i 和顺时针速度 它正在 V_i 上运行。 另外, 第i 个寿司的价值是 W_i 。

你现在是非负数 选择実数 t 。 还有时间 获取 t 坐标到 0 中存在的所有寿司。

找出您将获得的寿司总价值的最大可能值。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq L \leq 30
  • 0 \leq A_i < 2^L
  • 1 \leq V_i < 2^L
  • 1 \leq W_i \leq 10^9
  • 所有输入值均为整数

入力

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

N L
A_1 V_1 W_1
A_2 V_2 W_2
\vdots
A_N V_N W_N

出力

打印答案。 如果选择


入力例 1

3 2
3 1 1
2 2 2
1 1 3

出力例 1

5

例如 t=3 , 您可以获得第2 第 和 交换第 3 个寿司,其总价值为 对于 5 。


入力例 2

20 4
12 10 946667801
0 2 520643153
5 2 543856068
8 8 419370025
11 5 910500853
2 3 715892722
15 8 459924868
4 8 950300099
7 2 504976377
11 1 152036485
15 4 361324668
7 14 628902494
12 12 69837030
7 7 596982638
1 10 222135106
3 14 210989591
13 6 935147464
13 2 362117198
11 4 909241708
1 8 487330736

出力例 2

1705145758