装备配置（equipment）

题目描述

某探险队准备挑选一批装备。

共有 n 件装备，每件装备最多选择一次。

第 i 件装备的重量为 $w_i，实用价值为 v_i$。

背包最大承重为 V。

由于装备管理规定，最终选择的装备中，重量为奇数的装备必须恰好有 KK 件。

重量为偶数的装备没有件数要求，但每件同样最多只能选择一次。

求满足所有条件时能够获得的最大总价值。

如果不存在满足要求的选择方案，输出 -1。

输入格式

第一行三个整数 $KV,n,K$。

接下来 n 行，每行两个整数 $w_i,v_i$。

输出格式

输出最大总价值，无解输出 -1。

输入样例

10 5 2
3 6
5 10
2 7
4 8
1 3

输出样例

24

样例解释

选择重量为 3,2,4,1 的四件装备。

总重量为 3+2+4+1=10。

其中恰好有两件装备的重量为奇数：3 和 1。

总价值为 6+7+8+3=24。

数据范围

• 1≤n≤60
• 1≤V≤1000
• 0≤K≤n
• 1≤wi≤1000
• 1≤vi≤10000