(А.Богданов) Аналитическое агентство моделирует распределение нефти между отраслями экономики Китая на следующий год.

Поступило N заявок от предприятий.

Каждая заявка содержит объём нефти в тысячах тонн и код отрасли: 1 – транспорт, 2 – нефтехимия, 3 – промышленность и энергетика, 4 – прочие потребители.

Общий объём, доступный для распределения, равен S тыс. т.

Заявка удовлетворяется только полностью.

Распределение проводится в два этапа.

На первом этапе удовлетворяется максимально возможное количество заявок нефтехимической отрасли.

На втором этапе из оставшегося объёма удовлетворяется максимально возможное количество заявок остальных отраслей.

Определите общее количество удовлетворённых заявок.

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

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

В первой строке входного файла записаны два натуральных числа: S (не больше 10⁹) и N (не больше 10 000).

В каждой из следующих N строк записаны два натуральных числа: объём заявки (не больше 10 000) и код отрасли.

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

В ответе запишите два числа: сначала общее количество удовлетворённых заявок, затем максимальный объём заявки.

Пример входного файла

150 10

40 2

25 2

60 2

35 2

30 1

50 1

20 3

45 3

15 4

70 4

Разбор примера.

Заявки нефтехимии в порядке возрастания: 25, 35, 40, 60.

Первые три дают в сумме 100, поэтому удовлетворяются 3 заявки и остаётся 50.

Остальные заявки в порядке возрастания: 15, 20, 30, 45, 50, 70.

В остаток 50 помещаются две из них (15 + 20 = 35).

Итого 3 + 2 = 5 заявок.

Чтобы вторая часть ответа была максимальной, берём 15 и ищем самую большую заявку, не превышающую 50 - 15 = 35.

Это 30.

Ответ для примера: 5 30