U122406 最后一题

“呼，终于只剩下最后一题了呢...” World Finals 还剩 1 小时就要封榜，已经 AC 了其他题目的小 X 点开了最后一题。

时钟的秒针“滴答”的转着，纵使草稿纸上全是演算记录，但是小 X 苦思冥想，却想不出来最后一题的正解。 作为小 X 的队友，你凑上去看了看题目： > **L. 线性规划** > > 给定三个长度为 $n$ 的数列 $\{a_1, a_2, \cdots, a_n\}$，$\{b_1, b_2, \cdots, b_n\}$，$\{c_1, c_2, \cdots, c_n\}$。 > > 你需要找到一个长度为 $n$ 的 0-1 数列 $\{x_1, x_2, \cdots, x_n\}$，使得这个 0-1 数列在满足 $a_1x_1 + a_2x_2 + \cdots + a_nx_n \leq P$，$b_1x_1 + b_2x_2 + \cdots + b_nx_n \geq P$ 的情况下，能使 $w = c_1x_1+c_2x_2 + \cdots + c_nx_n$ 最小。 时间所剩无几，你们能否 AK World Finals，就靠你了！

第一行一个整数 $T$，表示测试数据的数量。 对于每组测试数据： 第一行为两个正整数 $n$，$P$。 第二行为 $n$ 个非负整数，第 $i$ 个数表示 $a_i$。 第三行为 $n$ 个非负整数，第 $i$ 个数表示 $b_i$。 第四行为 $n$ 个非负整数，第 $i$ 个数表示 $c_i$。

对于每组测试数据： 如果存在一个 0-1 数列，使得题面中的的约束能被满足，请输出一行一个整数，表示 $w$ 的最小值。 否则请输出 ``Bad Luck``。

**样例 #1 解释** 对于第一组数据，一个符合条件的 0-1 数列为 $\{1,0,0,1,0\}$。 此时 $1 \times 1 + 3 \times 0 + 6 \times 0 + 10 \times 1 + 13 \times 0 = 11 \leq 25$，$13 \times 1 + 7 \times 0 + 8 \times 0 + 15 \times 1 + 16 \times 0 = 28 \geq 25$，此时 $w$ 有最小值 $4$。 对于第二组数据，很明显没有符合条件的 0-1 数列。 **数据范围** 对于 $100\%$ 的数据，$T \leq 5$，$n \leq 1000$，$a_i \leq b_i$，$a_i,b_i,P \leq 10^4$，$c_i \leq 2 \times 10^6$。 **子任务** **本题捆绑测试。** 以下设 $Test$ 为测试点编号。 * 子任务 1（测试点 1~7，17 分）：$n = 10 + Test$ * 子任务 2（测试点 8~14，31 分）：$n = 970 + Test$，$a_i,b_i,P \leq 100$ * 子任务 3（测试点 15~21，19 分）：$n = 970+Test$，所有 $c_i=0$ * 子任务 4（测试点 22~30，33 分）：除 $n=970+Test$ 外无任何限制 同一个测试点内的所有测试数据，都符合该测试点在子任务的特征。为了方便你识别数据特征，同一个测试点内的 $n$ 都相同。