当前没有测试数据。

恰好K件的装备组合

题目描述

雇佣兵小队准备执行潜入行动，背包容量为 $W$，且为了便于操作，队长要求恰好携带 $K$ 件装备。有 $n$ 件备选装备，每件有体积和价值，只能取或不取。请在总占用体积不超过 $W$ 且件数恰好为 $K$ 的前提下，使总价值最大；如果无法满足条件，输出 $-1$。

输入格式

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

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

输出格式

输出一个整数，表示满足条件时的最大总价值；若无法满足输出 $-1$。

输入输出样例 #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