← 返回题目
题库练习 买粮食
← 上一题 下一题 →

A71364 | 买粮食

来源编程题
时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

A 学校的食堂来市场上采购粮食，他们准备了 n 元，市场上有 m 种不同的粮食，每种粮食都是袋装的，只能整袋购买；不同种类的粮食价格、重量、袋数有差异（也可能相同，比如：大米和小米，可以是同一个重量的包装）。

请问：食堂以有限的资金，最多能购买到多少公斤的粮食。

输入格式

本题有多组测试数据，第1行读入一个整数t代表测试数据的组数。（t \le 10）

对于每组测试数据，先读入两个整数 n 和 m 。(1 \le n \le 100, 1 \le m \le 100)

接下来 m 行，每行有 3 个整数 x , y , z ，分别代表每种粮食的价格、重量、袋数。 (1 \le x \le 20,1 \le y \le 200,1 \le z \le 20)

输出格式

对于每组测试数据，请输出能够购买粮食的最多重量，食堂准备的经费可能买不光所有的大米，经费可以不用完。每组输出占一行。

输入输出样例

输入 #1
1
42 6
10 1 15
19 79 5
6 65 3
8 82 6
16 92 2
17 28 3
输出 #1
441
C++ 编辑器
输入
输出