← 返回题目列表

AtCoder · tkppc6_1_n

N. 跳跃和行走

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

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

原案: 阿斯皮