题目描述

给定 $n$ 件物品的体积 $w_i$ 与价值 $v_i$ ，以及背包的总容量 $W$ 。

你可以优先选择 $k$ 件物品不消耗背包容量获得他们的价值，随后再选择一些物品，要求随后选择的物品的体积之和不超过 $W$ 。

请最大化选择物品的价值之和。

输入格式

输入的第一行包含三个整数 $n$ 、 $W$ 和 $k$ ( $1 \leq n \leq 5 \times 10^3$ 、 $1 \leq W \leq 10^4$ 、 $0 \leq k \leq n$ )，分别表示物品的总数、背包的总容量以及你可以免费拿走的物品数量。

在接下来的 $n$ 行中，第 $i$ 行包含两个整数 $w_i$ 和 $v_i$ ( $1 \leq w_i \leq W$ ， $1 \leq v_i \leq 10^9$ )，表示第 $i$ 个物品的体积和价值。

输出一行，一个整数表示答案。