Cai0715的花园
测试数据来自 system/1689
背景
为了帮助菌国的百姓,不让他们受病毒的折磨。同是也为了击退小毒物的攻击。嘟嘟受到高人(不,是高菌~)的指示,要去采花,用花粉来制造解药。于是,他找到了cai0715,希望获得他的帮忙。Cai0715说,要我帮忙可以,不过先答对我的问题吧。
描述
Cai0715拥有一个花园,这个花园非常的小,把它看作棋盘的话,只有3*3个格子的大小。初始时每个格子都是没有花的,所以需要种一些花卉使得花园变得美丽一点。
现在,Cai0715的手上有四种类型的花,杜鹃花、山茶花、牡丹花、水仙花,每种类型的花都拥有一个美丽值且无限量供应。你可以按照下面的规则种花。
1、你可以在任意格子种植杜鹃花。
2、如果想种植山茶花,则当时与它相邻的某个格子里必须有杜鹃花。
3、如果想种植牡丹花,则当时与它相邻的某个格子里必须有杜鹃花和山茶花。
4、如果想种植水仙花,则当时与它相邻的某个格子里必须有杜鹃花、山茶花和牡丹花。
5、每个格子不能同时栽种两种花。
6、如果两个格子相邻,当且仅当它们拥有一条公共边。
7、每种植一次花,需要花费单位1的时间。
8、你可以在任意时刻铲除某个格子的花,不需要花费时间。
现在,给定你每种花的美丽值,让你求出最少需要多少时间,可以使得花园的美丽值不低于Cai0715要求的最低美丽值W。如果怎样都无法达到,请输出Impossible。(花园的美丽值=Sum[每个格子中花的美丽值])
格式
输入格式
第一行1个数,N,代表共有N个测试点。
以下N行,每行5个数,Wb,Wr,Wg,Wy,W,分别代表杜鹃花、山茶花、牡丹花、水仙花的美丽值和Cai0715要求的最低美丽值。
输出格式
共N行,每行一个数,最少需要的时间,或Impossible。
样例1
样例输入1
4
1 1 1 1 3
1 2 4 8 21
1 1 1 100 500
7 20 53 94 395
样例输出1
3
7
Impossible
11
限制
各个测试点2s
提示
对于 30% 的测试数据,1<=Wb,Wr,Wg,Wy<=100,W<=100,N<=1。
对于 60% 的测试数据,1<=Wb,Wr,Wg,Wy<=10^8,W<=10^8,N<=10。
对于 100% 的测试数据,1<=Wb,Wr,Wg,Wy<=10^8,W<=10^8,N<=1000。
注意时限是2S