問題文

長さ 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
• 入力される値はすべて整数である

入力例 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