Модуль: Перебор всех подмасок данной маски


Задача

4 /7


Максимальная прибыль

Задача

Вы работаете менеджером и составляете план работ на следующий месяц. Каждый месяц разделён на T равных единиц времени. Всего имеется n задач, которые необходимо сделать. Однако, вы понимаете, что, возможно, успеть сделать все задачи за месяц не получится и хотите составить оптимальный план, выбрав для выполнения некоторые из них.

Про каждую задачу известно время ti, которое нужно затратить, чтобы сделать её, а также прибыль pi, которую сделанная задача принесёт компании. Вы хотите включить в план некоторые задачи так, чтобы:

  • Суммарное время, затраченное на выполнение задач, включённых в план, не превышало T.
  • Суммарная прибыль от выполнения этих задач была максимальна.
Составьте план, обладающий описанными выше свойствами и определите прибыль, получаемую в результате выполнения этого плана.

Обратите внимание на то, что единственный подходящий под условия план может не содержать ни одной задачи.
 

Входные данные

В первой строке  находятся натуральные числа T (1 ≤ T ≤ 100 000) и n (1 ≤ n ≤ 10) - число единиц времени в месяце и число задач.

Следующие n строк содержат по два натуральных числа ti и pi (1 <= ti, pi <= 100 000) - время, которое необходимо затратить на выполнение i-й задачи и прибыль, которую можно получить, выполнив её.


Выходные данные

Выведите единственное число — максимальная прибыль, которую можно получить, составив план, удовлетворяющий написанным выше условиям.

 
Примеры
Входные данные Выходные данные
1 10 3
8 100
3 10
3 10
100
2 10 4
5 10
5 20
2 5
2 6
31



time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Java3
Python16
С++ Mingw-w6432
Комментарий учителя