4297. [TIOJ - 114學年度複試] Constructive

【题目背景】

pooh 很想买 Ina 的五周年纪念商品，因此他决定要去打工。 他的打工是要去帮忙盖向量，这是一个很构造性 (Constructive) 的工作。现在有 $N$ 种长度小于 10 的二维向量（一个二维向量 $(a, b)$ 的长度为 $\sqrt{a^2 + b^2}$），每种 pooh 都可以取用无限多个。

但取用向量是有代价的，这 $N$ 种向量的代价分别为 $c_1, c_2, \dots, c_N$，每取用一个向量 $v_i$，pooh 的老板就需要付 $c_i$ 元。

【题目描述】

现在 pooh 的老板想要他用最小的代价取用向量，让他取用的向量总和为某个目标向量 $u = (x, y)$。请帮 pooh 确定是否有办法取用某些向量让它们的和为 $u$，如果可以的话，pooh 的老板最少需要付几元？

换句话说，给定 $N$ 个向量 $v_1, v_2, \dots, v_N$ 与 $N$ 个代价 $c_1, c_2, \dots, c_N$，请判断是否存在一组非负整数 $\alpha_1, \alpha_2, \dots, \alpha_N$ 满足： $$u = \alpha_1 v_1 + \alpha_2 v_2 + \dots + \alpha_N v_N$$ 如果存在，请输出在满足前式的状况下，$\sum_{i=1}^N \alpha_i c_i$ 最小可以是多。

【输入格式】

第一行包含三个整数 $N, x, y$，代表 pooh 可以取用几种向量与目标向量 $u = (x, y)$。
接着会有 $N$ 行，第 $i+1$ 行包含三个非负整数 $a_i, b_i, c_i$，代表第 $i$ 种向量 $v_i = (a_i, b_i)$ 与其代价 $c_i$。

【输出格式】

如果不存在任何一组非负整数 $\alpha_i$ 使得向量和为 $u$，输出 -1。否则输出满足条件的最小代价总和。

【样例输入1】

3 4 9
1 3 2
3 4 1
2 3 1

【样例输出1】

5

【样例输入2】

2 5 7
4 2 1
2 2 4

【样例输出2】

-1

【样例说明】

对于样例测资 1，最佳的 $\alpha = (2, 0, 1)$。
计算过程：$2 \times (1, 3) + 0 \times (3, 4) + 1 \times (2, 3) = (2+0+2, 6+0+3) = (4, 9)$。
总代价为 $2 \times 2 + 0 \times 1 + 1 \times 1 = 5$。
对于样例测资 2，可以证明不存在任何一组解。

【数据规模与约定】

• $1 \le N \le 90$
• $0 \le x, y \le 10^9$
• $0 \le a_i, b_i \le 10$
• $\forall (i, j), i \neq j \Rightarrow (a_i \neq a_j \lor b_i \neq b_j)$
• $\sqrt{a_i^2 + b_i^2} \le 10$
• $1 \le c_i \le 10^9$
• 大洋里（仅提供子任务 $3$ 和子任务 $6$ 的样例各一个）
  

【来源】

114 学年度台湾省建国中学信息学科能力竞赛：复试