E-小G的数学难题_牛客练习赛79

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小G在APIO2021中遇到了一个数学难题，可是经过小G漫⻓的思索，发现还是始终不能窥见真谛。

具体描述下这个问题是这样的：有三个长度为 $n$ 的数列 $\left\{ a_{1}, a_{2}, . . . , a_{n} \right\}$ , $\left\{ b_{1}, b_{2}, . . . , b_{n} \right\}$ , $\left\{ c_{1}, c_{2}, . . . , c_{n} \right\}$ ，

需要满足约束：

1. $a_{1} \times x_{1}+a_{2} \times x_{2}+...+a_{n} \times x_{n} \leq P$

2. $b_{1} \times x_{1}+b_{2} \times x_{2}+...+b_{n} \times x_{n} \geq P$

3. $∀i, x_{i}∈\left\{ 0,1 \right\}$

然后题目要求小G最小化 $w=c_{1} \times x_{1}+c_{2} \times x_{2}+...+c_{n} \times x_{n}$ 。

可是距离比赛结束只剩下半个小时了，小G现在非常着急，能否A掉这题并取得AK的好成绩拿到AU，就靠你了，加油！

输入描述:

第一行一个正整数 $T$ 表示数据组数， $T\leq5$ 。

对于每组测试数据：

第一行两个正整数 $n$ , $P$ ，其中 $n\leq1000$ , $P\leq10000$ 。

第二行 $n$ 个非负整数，第 $i$ 个数为 $a_{i}$ 。

第三行 $n$ 个非负整数，第 $i$ 个数为 $b_{i}$ 。

第四行 $n$ 个非负整数，第 $i$ 个数为 $c_{i}$ 。

其中 $a_{i}$ , $b_{i}$ , $c_{i}$ 满足 $a_{i} \leq b_{i} \leq 2\times10^{6}$ , $c_{i}\leq 2\times10^{6}$ 。

输出描述:

如果条件可以满足，输出最小化的 $w$ 值，反之输出"IMPOSSIBLE!!!"。

示例1

输入

复制

5
5 26
3 3 2 10 1 
7 10 13 16 3 
5 10 4 6 2 
5 25
1 3 6 10 13 
13 7 8 15 16 
2 3 10 2 7 
5 1
2 9 7 2 4 
4 10 7 6 7 
0 0 0 0 0 
5 7
2 6 1 9 11 
7 11 12 16 16 
1 7 8 4 5 
5 24
9 1 13 7 4 
13 14 14 13 6 
7 6 5 8 2

输出

复制

10
4
IMPOSSIBLE!!!
1
11