2424 - 买粮食

题目描述

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

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

输入

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

对于每组测试数据,先读入两个整数 nm 。(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
42 6
10 1 15
19 79 5
6 65 3
8 82 6
16 92 2
17 28 3

输出

441
标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 145
通过人数 64
金币数量 1 枚
难度 入门


上一题 下一题