[POI1997]阿里巴巴

成绩 0 开启时间 2013年01月22日 星期二 04:30
折扣 0.8 折扣时间 2013年01月22日 星期二 04:30
允许迟交 关闭时间 2013年01月22日 星期二 04:30
输入文件 ali.in 输出文件 ali.out

想要“芝麻开门”,必须拥有一定数量的钱币,其中包括至少z枚金币,s枚银币和m枚铜币。 最初,阿里巴巴拥有三种钱币若干枚。他可以按照一定规则和芝麻之门的守护者进行交易。 每一种规则用以下形式表示:

z1, s1, m1 -> z2, s2, m2 (zi, si, mis属于集合{0,1,2,3,4})。

这样一种规则表示阿里巴巴可以将z1枚金币, s1枚银币, m1枚铜币换成z2枚金币, s2枚银币, m2枚铜币。 一次交易而得的钱币可以继续参加下一次的交易。

任务

从文件中读入几组数据;对于每一组数据:

  • 阿里巴巴最初拥有的金银铜三种钱币数目
  • “芝麻开门”所需的金银铜三种钱币数目
  • 所有交易规则

对每一组数据,判断是否存在有限次的交易,使阿里巴巴能开启芝麻之门。如果是,则将最少交易次数输出,否则在输出NIE(波兰文NO)

把结果写进文件中

输入格式 文件的第一行有一个整数d<=10,表示数据的组数。

接下来是d组数据,每组占若干行。

第一行是三个数zp, sp, mp ,属于集合{0,1,2,3,4}。表示阿里巴巴最初拥有的金银铜数目。

第二行是三个数z, s, m , 属于集合{0,1,2,3,4}。表示芝麻开门所需的金银铜数目。

第三行是规则总数r,1<=r<=10。

以下r行每行有六个数z1, s1, m1, z2, s2, m2 ,属于集合{0,1,2,3,4}。表示一种简单的交易z1, s1, m1 -> z2, s2, m2。

数字之间由若干个空格隔开。

输出格式

文件的第i行为第i组数据的答案:

一个非负整数——阿里巴巴要开启芝麻之门所需的最少交易次数,或者

单词NIE(波兰文NO)

样例输入

2
2 2 2
3 3 3
3
0 1 1 2 0 0
1 0 1 0 2 0
1 1 0 0 0 2
1 1 1
2 2 2
4
1 0 0 0 1 0
0 1 0 0 0 1
0 0 1 1 0 0
2 0 0 0 2 2

样例输出

NIE
9