配点 : 600 点
問題文
左右一排 N 方块从左侧开始排列。 它的编号为 1,2,\ldots,N 。从现在开始,阿斯皮君将在这些广场上移动。
阿斯皮君是第一个质量 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
阿斯皮君是质量 我想转到 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)
- 所有输入均为整数 如果有办法做到
入力
输入是按以下格式从标准输入给出的。
N K
A_1 B_1 C_1
A_2 B_2 C_2
\hspace{1.2cm}\vdots
A_{N-1} B_{N-1} C_{N-1}
出力
阿斯皮·昆加马斯
如果可以移动到 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
阿斯皮君是质量 我想转到 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 。
原案: 阿斯皮