2014
02-17

# Ingredient

Adam C. Murphy loves drinking, thus he collected all kind of drinks in his apartment. One day he felt boring, so he tried to mix a brand new kind of drink out of the old ones. After searching around his collections, he found that he had N (N<=10) kind of drinks. Each drink is composed of N ingredients. You can refer to Sample Input for more details. What Adam C. Murphy wants to do was to create a kind of mixture, which all the N ingredients had a certain ratio.

All the content in N drinks is given in integer, for example, {20, 45, 10, 3, 3} indicates a kind of drink with 81 volume with 20,45,10,3,3 for each different ingredients. Adam C. Murphy cherish his drinks so much that he will use either one whole bottle or not a drop of it, and he wanted to make this mixture out with least numbers of bottles.

Now Adam C. Murphy asks you for help. He wants to do it with minimum quantities of drinks, or if it was impossible at all.
You may assume Adam C. Murphy’s drinks are unlimited in quantity, and each kind of drink is unique, i.e. any kind of drink can’t be mixed from other N-1 drinks.

Input contains several test cases.
For each test case:
The first line is N (N<=10), represents the number of kinds.
The second line has N integer, which describes Adam C. Murphy’s ideal combination of ingredients.
Last N line, each line has N integer, which indicates each i-th (1<=i<=N) drink’s ingredients.

Input contains several test cases.
For each test case:
The first line is N (N<=10), represents the number of kinds.
The second line has N integer, which describes Adam C. Murphy’s ideal combination of ingredients.
Last N line, each line has N integer, which indicates each i-th (1<=i<=N) drink’s ingredients.

3
3 4 5
1 2 3
3 7 1
2 1 2

8 1 5 7

Hint
Hint

During the process, 64-bit integer will be enough.


1. 您没有考虑 树的根节点是负数的情况， 若树的根节点是个很大的负数，那么就要考虑过不过另外一边子树了