限定件数的装备挑选

题目描述

一支探险队要从仓库挑选装备装入背包。背包容量为 $W$，同时队长规定最多只能携带 $K$ 件装备以减轻负担。有 $n$ 件装备，每件装备有体积和价值，只能取或不取。请在不超过容量且件数不超过 $K$ 的前提下，让装备总价值最大。

输入格式

第一行包含三个整数 $n,W,K$。

接下来 $n$ 行，每行包含两个整数，表示一件装备的体积与价值。

输出格式

输出一个整数，表示可获得的最大总价值。

输入输出样例 #1

输入 #1

5 10 3
4 6
3 5
2 4
6 9
1 2

输出 #1

15

数据范围

对于 $100\%$ 的数据，$1 \le n \le 200$，$1 \le W \le 2000$，$1 \le K \le n$，体积与价值均在 $[1,10^4]$。EOF