Олимпиадный тренинг

Задача . Тяжелая, вариант-2


Задача

Темы:

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

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

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

 

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

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

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

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

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

Ввод Вывод
10 3
6 20
2 7
3 4
5


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

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