#929. 青蛙跳石头

青蛙跳石头

样例下载

题目描述

河面中露出 nn 块石头排成一行,自左向右依次编号为 11 ~ nn,编号为 ii 的石头高出水面的高度为 HiH_i,跳到这块石头上会消耗体力值 WiW_i。

有一只青蛙,已经从岸边跳到了 11 号石头上,它的目标是跳到第 nn 块石头上。它只能向右跳,并且跳跃距离有限,最远跳跃 kk 块石头的距离。假设当前它在第 xx 块石头上,那么它最远只能跳到第 x+kx + k 块石头上,并消耗所跳到的那块石头相应的体力值;同时,如果它跳到的那块石头的高度不小于当前所在石头的高度,那么它会额外消耗 dd 的体力值(d∈{0,1}d ∈ \{0, 1\})。

求青蛙跳到第 nn 块石头消耗的体力值之和最小是多少?

输入格式

第一行:三个整数 n,k,dn, k, d。

接下来 nn 行:每行两个整数 HiH_i 和 WiW_i。

输出格式

一个整数,表示答案。

样例输入

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%的数据,n≤1000n ≤ 1000;

对于另外40%的数据,d=0d = 0;

对于100%的数据,$1 ≤ k < n ≤ 3 × 10^5, 0 ≤ H_i ≤ 10^9, 0 ≤ W_i ≤ 10^3, d ∈ \{0, 1\}$