Васин жесткий диск состоит из M секторов. Вася последовательно устанавливал на него различные операционные системы следующим методом: он создавал новый раздел диска из последовательных секторов, начиная с сектора номер ai и до сектора bi включительно, и устанавливал на него очередную систему. При этом, если очередной раздел хотя бы по одному сектору пересекается с каким-то ранее созданным разделом, то ранее созданный раздел «затирается», и операционная система, которая на него была установлена, больше не может быть загружена.
Напишите программу, которая по информации о том, какие разделы на диске создавал Вася, определит, сколько в итоге работоспособных операционных систем установлено и работает в настоящий момент на Васином компьютере.
Формат входных данных
Сначала вводятся натуральное число M — количество секторов на жестком диске (1 ≤ M ≤ 109) и целое число N — количество разделов, которое последовательно создавал Вася (0 ≤ N ≤ 1000).
Далее идут N пар чисел ai и bi, задающих номера начального и конечного секторов раздела
(1 ≤ ai ≤ bi ≤ M).
Формат выходных данных
Выведите одно число — количество работающих операционных систем на Васином компьютере.
Input:
10
3
1 3
4 7
3 4
Output:
1
Вы решили заказать пиццу с доставкой на дом. Известно, что для клиентов, сделавших заказ на сумму более \(C\) рублей, доставка является бесплатной, при заказе на \(C\) рублей и меньше доставка стоит \(B\) рублей. Вы уже выбрали товара стоимостью \(A\) рублей. В наличии имеются еще \(N\) товаров стоимостью \(d_1, ..., d_N\) рублей, каждый в единственном экземпляре. Их также можно включить в заказ. Как потратить меньше всего денег и получить на дом уже выбранный товар стоимостью \(A\) рублей?
Вводятся сначала числа \(A, B, C, N,\) а затем \(N\) чисел \(d_1, ..., d_N\). Все числа целые, \(1 \le A \le 1000, 1 \le B ≤ 1000, 1 \le C \le 1000, 0 \le N \le 1000, 1 \le di \le 1 000 000\).
Выведите единственное число – суммарное количество денег, которое придется потратить.
10 17 25 5 2 7 5 3 7
26
100 1 50 5 5 2 4 3 1
100
10 14 25 5 2 7 5 3 7
24
На День учителя Вася решил купить букет цветов. В магазине продаются ромашки по A рублей за штуку и гладиолусы по B рублей за штуку (A < B). У Васи есть C рублей. Он хочет составить букет из максимально возможного количества цветов, и при этом потратить как можно больше денег. Другими словами, из всех букетов с максимально возможным количеством цветов он хочет выбрать самый дорогой, но не дороже C рублей. Помогите ему вычислить стоимость такого букета.
Вводятся три целых числа A, B, C (1 ≤ A < B ≤ 100, 0 ≤ C ≤ 1000).
Выведите одно число — стоимость самого дорогого букета из максимального количества цветов.
В первом тесте искомый букет состоит из четырёх ромашек и одного гладиолуса. Во втором — только из трёх ромашек.
2 3 11
11
3 5 10
9
Компания из M человек пришла в пиццерию. Посовещавшись, они решили заказать одну большую пиццу с K начинками. Пицца представляет собой круг, поделённый на K равных секторов, в каждом из которых находится своя начинка. Пиццу подают ещё не разрезанной.
Друзья попросили официанта разрезать пиццу на M равных секторов, по одному куску на человека, так, чтобы как можно большему количеству людей достался кусок по крайней мере с двумя начинками.
Помогите официанту определить, какому именно количеству людей достанется больше одной начинки, если резать пиццу наиболее оптимально.
Вводятся два целых числа K, M (1 ≤ K ≤ 100, 1 ≤ M ≤ 100) — количество начинок в пицце и количество человек в компании соответственно.
Выведите количество человек, которым достанется более одной начинки в наилучшем случае.
В первом тесте каждому достанется по две начинки, если резать как угодно, но не по границам секторов с начинками.
Во втором тесте не важно как резать: в любом случае обоим достанется по половине пиццы, в каждой из которых будет больше одной начинки.
3 3
3
3 2
2
В этой задаче Вася готовится к олимпиаде. Учитель дал ему N (1 ≤ N ≤ 100 000) задач для тренировки. Для каждой из этих задач известно, каким умением ai нужно обладать для её решения. Это означает, что если текущее умение Васи больше либо равно заданного умения для задачи, то он может ее решить. Кроме того, после решения i-й задачи Васино умение увеличивается на число bi.
Исходное умение Васи равно A. Решать данные учителем задачи он может в произвольном порядке. Какое максимальное количество задач он сможет решить, если выберет самый лучший порядок их решения?
Сначала вводятся два целых числа N, A (1 ≤ N ≤ 100 000, 0 ≤ A ≤ 109) — количество задач и исходное умение. Далее идут N пар целых чисел ai, bi (1 ≤ ai ≤ 109, 1 ≤ bi ≤ 109) — соответственно сколько умения нужно для решения i-й задачи и сколько умения прибавится после её решения.
Выведите одно число — максимальное количество задач, которое Вася сможет решить.
3 2 3 1 2 1 1 1
3