青蛙跳石头
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
河面中露出 块石头排成一行,自左向右依次编号为 ~ ,编号为 的石头高出水面的高度为 ,跳到这块石头上会消耗体力值 。
有一只青蛙,已经从岸边跳到了 号石头上,它的目标是跳到第 块石头上。它只能向右跳,并且跳跃距离有限,最远跳跃 块石头的距离。假设当前它在第 块石头上,那么它最远只能跳到第 块石头上,并消耗所跳到的那块石头相应的体力值;同时,如果它跳到的那块石头的高度不小于当前所在石头的高度,那么它会额外消耗 的体力值()。
求青蛙跳到第 块石头消耗的体力值之和最小是多少?
输入格式
第一行:三个整数 。
接下来 行:每行两个整数 和 。
输出格式
一个整数,表示答案。
样例输入
5 2 1
4 3
3 2
5 3
2 1
6 1
样例输出
8
样例解释
青蛙可以这样跳:1 → 2 → 4 → 5,消耗的体力值是 3 + 2 + 1 + 1,并在 4 → 5 时额外消耗 1 体力值。
数据范围
对于20%的数据,;
对于另外40%的数据,;
对于100%的数据,$1 ≤ k < n ≤ 3 × 10^5, 0 ≤ H_i ≤ 10^9, 0 ≤ W_i ≤ 10^3, d ∈ \{0, 1\}$