bzoj#P2826. Minecraft的世界末日

Minecraft的世界末日

题目描述

邪恶的 PureDark 星球的居民把曾经美丽的草原、森林、海洋、高山、沙漠变成了由工业 MOD 驱动的各类机器所构成的钢铁城市。可惜,这些居民或是因为水平不足,亦或是抱着一种不负责任的心态,无数次核弹的爆炸以及各类核电事故,加之植被被毁、空气污染,整个星球的环境已经恶化到了不可挽回的地步。就在这个时候,平日里被各种 OI 题目虐得死去活来的沙茶,突然人品爆发,发明出一种机器,这种机器能够把环境中的污染物转变成一种特殊的粒子——沙茶粒子(Sandy-tea Particle,简称STP),也可以将这种粒子放出重新变成污染物。PureDark 星球的居民发现,这是收集这种危险污染物的唯一方式。而由于污染物的量过于巨大,通过收集污染物的方式无法阻止环境恶化,因此人们并不重视这台机器,也没有人愿意协同沙茶完成自己的伟大设计,因此沙茶来到地球,找到了身为 OI 大牛的你。因为 Minecraft 世界中没有任何物理可言,沙茶可以通过一种叫做 Redstone 的物质无限地获取能源供机器运转而不需要付出任何费用或是高能的 STP,同时物质的转化也不再满足质量守恒的规律。也就是说,在某一天将污染物转化为 STP,在另一天可能可以以不同的比例转化回污染物。沙茶准备利用这种转化的比例差来产生更多的 STP,因为他预感到这种粒子可以起到拯救世界的作用,虽然他不知道如何用 STP 来拯救世界。很可惜沙茶终究是沙茶,他的机器能力非常有限,每天最多只能够转化污染物 GiG_imol 或是释放污染物 DiD_imol(这些值能事先被预测出来),转化和释放污染物不能在同一天进行,且转化的污染物的物质的量必须是整数。机器每次进行物质转化后,需要等待 TT 天使设备冷却,冷却过程中不能再进行物质转化。沙茶的机器有一个用于存储污染物的大仓,它的容积当然不是无限大的,最多能存储 CCmol 污染物。每次实验结束时,机器中的污染物必须被清空,沙茶可不愿意冒机器爆炸的险。也是因为 Minecraft 世界没有任何物理可言,STP 粒子可以以任意的密度存在,也就是说机器中的 STP 粒子可以无限多。同时,机器中 STP 粒子的物质的量可以为 00、为正整数,甚至可以为负整数。现在,沙茶想做 MM 次实验来测试机器的稳定性。在每次实验开始时,他拥有的 STP 的物质的量为 00。他预感到了第 ii 天每摩尔污染物需要 STP 的物质的量 AiA_i 以及这一天每摩尔污染物能转化成的 STP 的物质的量 BiB_i,以及前文提到的 GiG_iDiD_i 。请帮他算出他每次实验能获得的 STP 的最大值。

输入格式

11 行是一个正整数 MM,表示实验的次数。对于每次实验,第 11 行是三个正整数 N,T,CN,T,C,分别表示实验的天数、设备冷却时间和污染物存储器的容量。第 2255 行分别有 NN 个正整数,每行分别是 A1,A2A_1,A_2ANA_NB1,B2B_1,B_2BNB_NG1,G2G_1,G_2GNG_ND1,D2D_1,D_2DND_N,意义如前文所述。

输出格式

MM 行,每行一个整数,第 ii 行的整数表示沙茶在第 ii 次实验中能获得的最大 STP 的物质的量。

1
10 1 10
1 1 1 5 5 10 10 10 10 10
1 2 3 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
14

样例说明

一个最优方案为:在第 1,31,3 天各消耗 11 mol STP 转化为 11 mol 污染物,在第 7,97,9 天分别将 11 mol 污染物转化为 7,97,9 mol STP,整个实验结束时有 STP 7+9117+9-1-1mol=14=14mol。

数据规模与约定

0Ai,Bi,Gi,Di1000\le A_i,B_i,G_i,D_i\le100M10M\le10O,TN3000O,T<N\le30001C30001\le C\le3000

题目来源

湖北省队互测