F. 快乐程序竞赛

题目描述

给出比赛总时间和题目数，并给出每道题目的耗时以及获得的价值，求所能获得的最大价值，以及获得这个最大价值下的最多题目数，以及该情况的最小罚时（罚时为每道题目提交的时间之和）。

输入格式

首先给出测试数据数 $N < 50$，每个测试数据的第一行给出时间 $T \le 1000$ 和题目数 $n \le 50$，第二行给出完成题目所需的时间 $t_i \le 1000$，第三行给出完成题目的价值 $v_i \le 1000$。

输出格式

对于每种情况，按以下顺序输出一行，其中包含3个整数：总吸引价值、解决问题的数量、总惩罚时间。这3个整数应该用空格分隔。

样例

输入

2
300 10
10 10 10 10 10 10 10 10 10 10
1 2 3 4 5 6 7 8 9 10
300 10
301 301 301 301 301 301 301 301 301 301
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

输出

55 10 550
0 0 0

数据范围与提示

• 测试数据数 $N < 50$
• 比赛总时间 $T \le 1000$
• 题目数 $n \le 50$
• 单题耗时 $t_i \le 1000$
• 单题价值 $v_i \le 1000$