P2729 [USACO3.2] 饲料调配 Feed Ratios

农夫约翰从来只用调配得最好的饲料来喂他的奶牛。饲料用三种原料调配成：大麦，燕麦和小麦。他知道自己的饲料精确的配比，在市场上是买不到这样的饲料的。他只好购买其他三种混合饲料（同样都由三种麦子组成），然后将它们混合，来调配他的完美饲料。

给出三组整数，每组整数表示一种饲料中大麦、燕麦与小麦的比例，找出用这三种饲料调配 $x:y:z$ 的饲料的方法。 请编写一个程序找出使这三种饲料用量最少的方案，要是不能用这三种饲料调配目标饲料，输出一行一个字符串 `NONE`。“用量最少”意味着三种饲料的用量（整数）的和必须最小。 例如，要求使用 $1:2:3$、$3:7:1$、$2:1:2$ 的饲料调配 $3:4:5$ 的饲料，我们可以通过 $8$ 份第一种饲料、$1$ 份第二种饲料和 $5$ 份第三种饲料调配 $7$ 份目标饲料。这是因为 $8 \times 1 + 1 \times 3 + 5 \times 2 = 21$，$8 \times 2 + 1 \times 7 + 5 \times 1 = 28$，$8 \times 3 + 1 \times 1 + 5 \times 2 = 35$，而 $21:28:35$ 恰好等于 $3:4:5$。

第一行，三个整数 $x,y,z$，表示目标饲料中大麦、燕麦与小麦的比为 $x:y:z$。 接下来三行，第 $i$ 行三个整数 $a_i,b_i,c_i$，表示第 $i$ 种饲料中大麦、燕麦与小麦的比为 $a_i:b_i:c_i$。 数据保证输入的所有整数在 $0 \sim 99$ 之间，且每一行的三个整数不会同为 $0$。

如果能够用这三种饲料调配出目标饲料，则输出一行 $4$ 个整数，前三个整数 $m,n,p$ 分别代表三种饲料的份数，第四个整数代表得到目标饲料的份数。如果有多解，输出 $m+n+p$ 最小的一组。如果不能用这三种饲料调配出目标饲料，输出一行一个字符串 `NONE`。数据保证如果有解， $m+n+p$ 最小的解只有一组。

题目翻译来自NOCOW。 USACO Training Section 3.2