Информатика

Примеры

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

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

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

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

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

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

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

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

Вы занимаетесь разработкой системы по продаже билетов на поезда. Несмотря на то, что поезда ходят по множеству различных маршрутов, вы будете работать только с одним из них. Маршрут рассматриваемого поезда состоит из n остановок: маршрут начинается в первой из них, а заканчивается в n-й, соответственно. Всего в поезде имеется m мест для пассажиров.

Эта система будет использоваться для продажи билетов пассажирам. При покупке билета пассажир указывает номер станции L, на которой он хочет сесть на поезд и номер станции R, на которой он хочет сойти с поезда. Если у одного пассажира есть билет до станции S, а другой хочет купить билет от станции S, то они друг другу не мешают: второй может занимать только что освободившееся место первого. Система должна сообщить пассажиру следующую информацию:

• f, где f  число свободных мест мест между L-й и R-й станциями, если хотя бы одно такое место есть. В этом случае пассажир покупает один билет с L-й по R-ю станцию.
• 0 если подходящих свободных мест нет. В этом случае пассажир билет не покупает.

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

В первой  находятся натуральные числа n (2 ≤ n ≤ 100), m (1 ≤ m ≤ 100) и k (1 ≤ k ≤ 100) — число станций в маршруте поезда, максимальное число пассажиров в поезде и число обращений обращений пассажиров к системе покупки билетов.

Следующие k строк содержат по два натуральных числа L_i и R_i (1 ≤ L_i < R_i ≤ n)  — начальная и конечная станции в i-м обращении к системе.

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

Для каждого запроса на покупку билета в своей строке выведите ответ системы: число билетов, которые можно купить на данный маршрут, или 0, если ни одного билета купить нельзя.

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

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

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

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

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

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

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

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

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

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

Примеры

Пете подарили n гирь и чашечные весы. Каждая гиря весит a_i грамм. Первым делом он разложил гири на чаши. При этом одна из чаш может быть пустой. Теперь он хочет выяснить, какой наименьшей разницы весов на чашах можно достичь, не более чем за два перекладывания гирь.

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

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

В первой строке находится одно натуральное число n (1 ≤ n ≤ 50) — количество гирек.
В каждой из следующих n строк находятся два натуральных числа a_i, b_i (1 ≤ a_i ≤ 1000, 1 ≤ b_i ≤ 2) — масса гири и номер чаши весов, на которой она находится.

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

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

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

На складе хранятся ящики разных цветов и размеров. Каждый цвет и каждый размер имеют свой порядковый номер в информационной системе.

Перед отправкой ящики упаковывают и сортируют. Упаковка и сортировка ящиков неэффективна и происходит следующим образом:

• Ящик под номером i поступает на склад.
• Ищется стопка, в которой хранятся ящики с размером, равным размеру i-го. Если такой стопки нет, формируется новая стопка.
• Поступающий ящик помещается наверх найденной или сформированной стопки.
• Если в какой-либо стопке оказывается два верхних ящика одного цвета, то они запаковываются и отправляются адресату.

Ваша задача написать программу, которая сможет оценить эффективность данной системы и посчитает сколько ящиков останутся на складе. 
 

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

В первой строке находятся три натуральных числа n, m, k (1 ≤ n, m, k ≤ 100) — количество ящиков, поступающих на склад, количество различных размеров и количество различных цветов соответственно.
В каждой из следующих n строк находятся по два натуральных числа x_i и y_i (1 ≤ x_i ≤ m; 1 ≤ y_i ≤ k)  — номер размера и номер цвета ящика, который поступит i-м на склад.

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

Требуется вывести одно число — сколько ящиков останутся на складе, после выполнения отправки.

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

Примеры

5
10 20 25 30 35
30 40 50 60 70

3.000000 2.000000 2.000000 2.000000 2.000000
2.083333