Ali Baba

Time limit1sMemory limit128 MB

Summary

Given starting tokens and trade rules over three token types, find the minimum number of trades to reach at least the required counts per type, or NIE if impossible.

Level: Hard8 of 10
Topics: BFS, Graph, Shortest path, Implementation
Solved: No attempts yet

Problem

To open the cave of sesame, Ali Baba must be holding a set of tokens that contains at least $z$ gold tokens, $s$ silver tokens, and $m$ copper tokens. At the start he owns some number of tokens of each kind, and he may trade with the Guardian of the cave according to a fixed list of rules. Every rule has the form

$z_1, s_1, m_1 \to z_2, s_2, m_2 \qquad (z_i, s_i, m_i \in \{0, 1, 2, 3, 4\})$

meaning that Ali Baba may hand over $z_1$ gold, $s_1$ silver, and $m_1$ copper tokens and receive $z_2$ gold, $s_2$ silver, and $m_2$ copper tokens in return. Tokens gained in one trade may be spent in later trades.

For each test case, decide whether some finite sequence of trades lets Ali Baba end up holding at least the required number of tokens of every kind. If it does, report the smallest possible number of trades in such a sequence; otherwise report NIE (Polish for "no").

Input

The first line contains one positive integer $d$ ( $d \le 10$ ), the number of test cases. The test cases follow, each spanning several lines.

For every test case:

the first line holds three non-negative integers $z_p, s_p, m_p \in \{0, 1, 2, 3, 4\}$ , the numbers of gold, silver, and copper tokens Ali Baba owns at the start;
the second line holds three integers $z, s, m \in \{0, 1, 2, 3, 4\}$ , the numbers of gold, silver, and copper tokens needed to open the cave;
the third line holds the number of rules $r$ ( $1 \le r \le 10$ );
each of the next $r$ lines holds six integers $z_1, s_1, m_1, z_2, s_2, m_2 \in \{0, 1, 2, 3, 4\}$ describing one rule $z_1, s_1, m_1 \to z_2, s_2, m_2$ .

Within every line the numbers are separated by single spaces.

Output

For each test case, print one line: either a single non-negative integer, the least number of trades Ali Baba must make in order to hold at least the required set of tokens, or the word NIE if no such sequence of trades exists.

Examples3

Example 1

Input

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

Expected output

NIE
9

Example 2
Input
```
1
1 0 0
0 1 0
1
1 0 0 0 1 0
```
Expected output
```
1
```
Example 3
Input
```
1
0 0 0
4 0 0
1
0 0 0 4 0 0
```
Expected output
```
1
```