DP604 限时爬山

难度梯度：T3+｜训练重点：二维资源 DP

题目描述

有 N 段山路，按顺序必须全部走完。第 i 段可步行，耗时 walk_i；或用一次体力加速，耗时 fast_i。最多能加速 K 段，求走完整条山路的最短时间。

加速只影响被选择的那一段，每段最多加速一次；允许少于 K 次或完全不加速。所有山路都必须走完。

输入格式

第一行 N K；随后 N 行 walk_i fast_i。

输出格式

输出最短总时间。

样例输入

3 1
5 2
4 1
3 2

样例输出

9

样例说明

第二段加速：5+1+3=9；第一段加速为 2+4+3=9。

数据范围

1≤N≤1000；0≤K≤100；1≤fast_i≤walk_i≤10^6。

子任务

30 分：N≤20；30 分：K=0；40 分：无附加限制。