1586 : 健康食谱

时间限制:1 Sec 内存限制:128 MiB
提交:158 答案正确:65

提交 状态 讨论区

题目描述

 月野兔很爱美丽。在没事的时候,她就研究了一下食谱,她了解到,每个人每天需要的热量有一个最大限度,但是她十分爱美食。于是古灵精怪的她就想在最大的热量范围内品尝到尽量多的美味,(每一种食物都有一个热量值和一个美味值),这么多的美食,她实在难以抉择,那么现在问题来了,你能帮她吗?

输入

 输入一个T(0<T<=20),有T组测试实例。

每组实例先输入一个n(0<n<=1000),m(0<m<=100),分别代表这天需要的最大热量为n,有m种食物。接下来m行,第行包括三个数a,b,c,分别代表这种食物共有a克,每克的热量b和美味值c(0<a,b,c<1000)(节约粮食,传统美德,少拿勤取, 食物是可以分割的)。

输出

对于每组输入,输出可以获得的最大的美味值x,保留两位小数。

样例输入

复制
3
10 3
3 3 3
4 5 6
5 4 3
12 4
1 2 3
2 4 3
5 4 6
3 2 4
5 2
1 5 6
2 6 5

样例输出

复制
12.00
21.00
6.00

提示


			

来源

14新生赛-wh