题目描述

小Z在ACM比赛中遇到了一个线性规划问题，经过漫长的思索，始终难以窥见真谛。

这个问题是这样的：有三个长度为$n$的数列$\{a_1, a_2, \ldots, a_n\},\{b_1, b_2, \ldots, b_n\},\{c_1, c_2, \ldots, c_n\}$，要满足约束

$a_1x_1+a_2x_2+\ldots+a_nx_n \le P$

$b_1x_1+b_2x_2+\ldots+b_nx_n \ge P$

$\forall i,x_i \in \{0,1\}$

最小化

$w=c_1x_1+c_2x_2+\ldots+c_nx_n$

比赛还剩半小时就要结束，小Z所在的队能否A掉这题并取得金牌，就靠你了。

格式

输入格式

一个测试点内含有$T$组测试数据，第一行为一个正整数$T$。

对于每组测试数据：

第一行两个正整数$n,P$。

第二行为$n$个非负整数，第$i$个数为$a_i$。

第三行为$n$个非负整数，第$i$个数为$b_i$。

第四行为$n$个非负整数，第$i$个数为$c_i$。

输出格式

对于每组测试数据：如果题目中的约束能被满足，你需要输出一个非负整数，代表$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

输出1

10
4
IMPOSSIBLE!!!
1
11

输入2

5
15 429
65 97 103 16 49 65 111 9 46 54 59 1 16 9 17 
124 110 120 75 83 101 112 91 49 94 97 34 54 124 34 
83 793 50 90 324 85 850 759 723 308 768 13 437 680 568 
15 435
26 14 28 19 14 37 37 36 68 42 87 42 8 61 12 
49 77 81 29 81 38 83 121 84 91 122 65 47 101 115 
276 51 157 260 401 541 810 74 360 209 797 795 527 802 99 
15 607
88 19 83 94 11 1 102 19 1 49 84 66 28 3 22 
107 119 124 119 109 17 127 34 97 80 113 90 125 49 72 
787 298 287 534 546 345 557 410 453 573 939 604 195 137 941 
15 529
27 51 109 65 108 32 52 8 16 13 7 26 78 57 66 
126 83 129 74 126 111 67 43 42 65 89 131 98 114 98 
173 654 285 390 662 198 353 333 76 440 790 616 530 440 188 
15 800
65 42 81 14 65 35 60 8 53 59 20 45 5 50 6 
71 49 119 102 110 114 62 108 119 126 62 98 100 51 62 
255 643 307 99 648 964 120 705 980 920 108 556 328 222 691

输出2

321
590
1871
1197
3007

输入3

见附件。

输出3

见附件。

点此下载附件

数据规模与约定

本题共有$20$个测试点。

对于$1\sim 5$号测试点，第$i$个测试点的所有$n=10+i$，$a_j,b_j,P\le 10000$；

对于$6\sim 10$号测试点，第$i$个测试点的所有$n=980+i$，$a_j,b_j,P\le 100$；

对于$11\sim 14$号测试点，第$i$个测试点的所有$n=980+i$，$a_j,b_j,P\le 10000$，且$c_j=0$；

对于$15\sim 20$号测试点，第$i$个测试点的所有$n=980+i$，$a_j,b_j,P\le 10000$。

同时，所有的测试点都满足$T\le 5,\ a_i\le b_i,\ c_i\le 2\times 10^6$。