Module: 遍历给定掩码的所有子模式

Problem

您担任经理并制定下个月的工作计划。每个月分为 T 个相等的时间单位。总共有 n 个任务需要完成。但是，您明白一个月内完成所有任务可能是不可能的，您希望通过选择其中一些任务来完成一个最佳计划。

对于每个任务，我们知道完成它需要花费的时间ti，以及利润pi< /sub> 完成的任务会给公司带来的。您想计划一些任务，以便：

• 在计划中包含的任务上花费的总时间不超过 T。
• 这些任务的总收益最大。

请注意，唯一符合条件的计划可能不包含任何任务。
 

输入 数据

第一行  包含自然数 T (1 ≤ T ≤ 100 000) 和 n (1 ≤ n &le ; 10) - 每月的时间单位数和任务数。

接下来的n 行分别包含两个自然数ti和pi  (1 <= t_i, p_i <= 100 000) - 时间花在完成第i任务以及完成任务可以获得的利润。

压印 数据

打印单个数字 —通过制定满足上述条件的计划可以获得的最大利润。

例子