g6-08018. 加维识别·综合 未做

小杨有 $T$ 组询问，每组首行给类型号 $t$；物品都只有一件、最多选一次：$t=1$ 输入「n V k」及 $n$ 行「w v」，求恰好选 $k$ 件、总重不超过 $V$ 的最大价值（无解输出 $-1$）；$t=2$ 输入「n V M」及 $n$ 行「v m k」，求体积、承重均不超过 $V$、$M$ 的最大价值；$t=3$ 输入「n」及一行 $n$ 个「w」，每颗石子分进两堆之一，求两堆重量差的最小值；$t=4$ 输入「n V」及 $n$ 行「w v」，求总重不超过 $V$ 的最大价值。

第一行一个整数 $T$。

接下来 $T$ 组，格式如上。

每组一行，一个整数。

输入 1

4
1 3 5 2
2 3
2 3
3 4
2 3 5 5
3 3 4
2 2 3
2 2 3
3 4
3 1 2 4
4 3 8
2 3
3 4
4 5

输出 1

7
7
0
9

组 4 是标准 0/1 背包：选第 2、3 件（重 7 ≤ 8）得 9。

$1\le T\le 6$；各组 $n\le 30$；$t=1$ 时 $V,k\le 200$；$t=2$ 时 $V,M\le 100$；$t=3$ 时 $w_i\le 10^9$；$t=4$ 时 $V\le 10^9$、$w_i,v_i\le 10^9$。