{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003ePP读了鲁滨逊漂流记之后,晚上立即就梦见自己也来到了一个杳无人烟的小岛上,这个小岛上有许多奇妙珍贵的元素。\u003c/p\u003e\n\u003cp\u003e可是PP只带了一个口袋,这个口袋最多只能装重量为M的物品。PP走遍了整个小岛,总结了岛上所有珍贵的元素:共N个种类, 每种元素重量不同,分别为w1, w 2, ... , w n,同时每个种类的元素价值也不同,分别为v 1,v 2, ..., v n。\u003c/p\u003e\n\u003cp\u003ePP想在自己的口袋中装尽可能大价值的元素。已知每种元素可以被拆开,价值与重量成正比。请PP在梦里的小岛中可以装多少价值的元素呢?\u003c/p\u003e\n"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e输入数据有多组。第1行是组数k,后面跟着k组输入。\u003c/p\u003e\n\n\u003cp\u003e每组测试数据占3行,第1行是一个正整数M (1 \u003c\u003d M \u003c\u003d 10000),表示口袋能装的重量。\u003cbr\u003e\n第2行是一个正整数N (1 \u003c\u003d N \u003c\u003d100),表示小岛上的元素种类。\u003cbr\u003e\n第3行有2n个正整数,分别为w 1, v 1, w 2, v 2, ... , wn, vn分别为第一种,第二种,...,第n种元素的总重量和总价值(1 \u003c\u003d w i \u003c\u003d 10000, 1 \u003c\u003d v i \u003c\u003d 10000)。\u003c/p\u003e\n"}},{"title":"Output","value":{"format":"HTML","content":"\n 输出k行,每行输出该组数据最多能拿的价值数。输出应精确到小数点后2位。\n "}},{"title":"Sample Input","value":{"format":"HTML","content":"\n \u003cpre\u003e2\n50\n4\n10 100 50 30 7 34 87 100\n10000\n5\n1 43 43 323 35 45 43 54 87 43\n\u003c/pre\u003e\n "}},{"title":"Sample Output","value":{"format":"HTML","content":"\n \u003cpre\u003e171.93\n508.00\n\u003c/pre\u003e\n "}}]}