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

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

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

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

Формат входного файла

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

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

Формат выходного файла

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

Пример входных и выходных данных