配点 : 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