#1340. 奖牌

奖牌

题目描述

正值 2020 东京奥运会举办,组委会正在筹备金银牌的制作。已知制作全部奖牌需要 aa 克黄金和 bb 克白银(铜?你家电线就有啊)。

然而众所周知,组委会经费有限。他们有 nn 块材料,打算从中提炼金银。第 ii 块材料含有 xix_i 克黄金和 yiy_i 克白银,价格为 wiw_i。求组委会制作所有奖牌需要的费用最小是多少。

数据保证组委会能制成全部奖牌。

输入格式

第一行为三个正整数 n, a, bn,~a,~b

接下来 nn 行,每行三个整数 xi, yi, wix_i,~y_i,~w_i

输出格式

输出一行一个正整数,表示最小费用。

30 75 261
3 21 6
2 1 0
2 8 5
8 23 6
2 11 9
1 26 7
5 23 1
5 8 3
3 3 2
5 30 9
8 5 0
5 6 2
3 21 9
8 26 4
3 28 9
4 19 9
6 21 6
2 25 2
1 21 8
5 8 9
7 23 3
4 28 8
8 21 7
2 3 2
6 8 7
1 24 8
4 28 9
8 15 5
1 29 6
3 22 4
54

说明

对于 40%40\% 的数据,n10n\le 10

对于 100%100\% 的数据,1n1031\le n\le 10^31a, b, xi, yi3001\le a,~b,~x_i,~y_i\le 3000wi10100\le w_i\le 10^{10}