«Ну не гномы, а наказание какое-то!», – подумала Белоснежка, в очередной раз пытаясь уложить гномов спать. Одного уложишь – другой уже проснулся! И так всю ночь.

У Белоснежки \(n\) гномов, и все они очень разные. Она знает, что для того, чтобы уложить спать \(i\)-го гнома нужно \(a_i\) минут, и после этого он будет спать ровно \(b_i\) минут. Помогите Белоснежке узнать, может ли она получить хотя бы минутку отдыха, когда все гномы будут спать, и если да, то в каком порядке для этого нужно укладывать гномов спать.

Например, пусть есть всего два гнома, \(a_1\) = 1, \(b_1\) = 10, \(a_2\) = 10, \(b_2\) = 20. Если Белоснежка сначала начнет укладывать первого гнома, то потом ей потребуется целых 10 минут, чтобы уложить второго, а за это время проснется первый. Если же она начнет со второго гнома, то затем она успеет уложить первого и получит целых 10 минут отдыха.

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

Шоу состоит из \(n\) небольших представлений, в каждом из которых могут участвовать или львы, или тигры (также может случиться, что в представлении не участвуют ни те, ни другие). Представление \(i\) начинается через \(s_i\) минут от начала шоу и продолжается \(t_i\) минут. При этом в некоторые моменты времени на сцене могут идти одновременно несколько представлений (в этом случае в них не могут участвовать разные виды хищников).

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

В связи с проведением в Ханты-Мансийске Всероссийской олимпиады школьников по информатике агентство авиаперевозок обязано перевезти самолётами всех участников олимпиады. Всего за \(m\) дней, пронумерованных от 1 до \(m\), из Москвы в Ханты-Мансийск хотят вылететь \(n\) пассажиров, в том числе и участники олимпиады.

Все желающие вылететь в Ханты-Мансийск заполнили анкеты, в которых указали информацию о возможных днях вылета и об участии в олимпиаде. Информация о возможных днях вылета \(i\)-го пассажира указана в виде пары чисел \((a_i, b_i)\). Это означает, что пассажир согласен вылететь в любой день, начиная с \(a_i\) и по \(b_i\) включительно, и не может вылететь в другие дни.

Самолёт из Москвы в Ханты-Мансийск вылетает всего один раз в день и вмещает не более \(k\) пассажиров. Необходимо распределить пассажиров по дням вылета таким образом, чтобы улетело как можно большее количество пассажиров, при этом все участники Всероссийской олимпиады должны улететь обязательно.

Напишите программу, определяющую распределение пассажиров по дням вылета, при котором максимизируется количество перевезённых пассажиров, или определяющую, что такого распределения не существует.

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

В наличии имеется N₁ кепок, N₂ маек, N₃ штанов и N₄ пар ботинок (1 ≤ N_i ≤ 100 000). Про каждый элемент одежды известен его цвет (целое число от 1 до 100 000). Комплект одежды — это одна кепка, майка, штаны и одна пара ботинок. Каждый комплект характеризуется максимальной разницей между любыми двумя его элементами. Помогите Глебу выбрать максимально стильный комплект, то есть комплект с минимальной разницей цветов.