問題文

左右一列に N 個のマスが並べられており、左から順に 1,2,\ldots,N と番号が振られています。これからこれらのマスの上を aspi くんが移動します。

aspi くんははじめマス 1 におり、以下の行動を繰り返します。

• 現在いるマスの番号を i とする。以下の条件をすべて満たす非負整数の組 (a,b) を 1 つ選び、a \times K+b マス右に進む。このとき、コスト C_i がかかる。
  • 0 \leq a \leq A_i
  • 0 \leq b \leq B_i
  • a \times K + b \leq N-i

aspi くんはマス N まで移動したいです。移動が可能かを判定し、可能なら必要な合計コストの最小値を求めてください。

制約

• 1 \leq K \lt N \leq 2 \times 10^5
• 0 \leq A_i \leq N (1 \leq i \leq N-1)
• 0 \leq B_i \lt K (1 \leq i \leq N-1)
• 1 \leq C_i \leq 10^9 (2 \leq i \leq N-1)
• 入力は全て整数

入力例 1

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

出力例 1

4

例えば以下のように移動するとよいです。

• マス 1 から、(a,b)=(1,1) としてマス 4 に移動する。このとき、コスト C_1=3 がかかる。
• マス 2 から、(a,b)=(0,1) としてマス 5 に移動する。このとき、コストは C_4=1 かかる。

上記の移動方法における合計コストは 4 であり、これより合計コストの小さくなる移動方法は存在しないため答えは 4 です。

入力例 2

3 2
0 0 6
1 1 3

出力例 2

-1

aspi くんはマス N まで移動することができません。A_i と B_i が共に 0 になる場合があることに注意してください。

入力例 3

10 4
5 3 892311419
3 1 517634394
9 2 78211774
5 2 247254316
3 3 238811568
3 0 654514160
2 0 680020633
7 2 683514900
9 2 540304649

出力例 3

892311419

この場合、マス 1 からマス 10 に一回の行動で移動するのが最善です。

原案: aspi