Задача A. Новогодняя ёлка-1

Автор:И. Олейников, М. Прокопьева
Входной файл: input.txt   Ограничение времени:1 сек
Выходной файл: output.txt   Ограничение памяти:4 Мб

Условие

В детском саду города N для празднования Нового Года установили ёлку и для её украшения закупили K разноцветных шаров.

Шары характеризуются своей массой. Елка характеризуется максимальным весом, который она может выдержать, при этом не упав. Красота елки равна количеству висящих на ней шаров. Так как дети хотят удивить Деда мороза, они хотят как можно красивее украсить ёлку, при этом она не должна упасть.

Вас просят написать программу, которая по заданным параметрам игрушек и ёлки определит максимально возможную красоту наряженной ёлки.

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

Во входном файле содержатся числа M и K — соответственно максимальный вес ёлки и количество купленных шаров. За ними следуют K чисел vi — вес i-того шара.

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

В выходном файле должно содержаться единственное число — максимально возможная красота наряженной ёлки.

Ограничения

1 ≤ M ≤ 1000 1 ≤ K ≤ 100000 1 ≤ vi ≤ 1000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2
1 2
2

Задача B. Новогодняя ёлка-2

Автор:И. Олейников
Входной файл: input.txt   Ограничение времени:1 сек
Выходной файл: output.txt   Ограничение памяти:4 Мб

Условие

В детском саду города N для празднования Нового Года установили ёлку и для её украшения закупили K елочных игрушек.

Елочные игрушки характеризуются двумя параметрами — массой и красотой. Елка также характеризуется двумя параметрами — максимальной массой игрушек, которую она может выдержать и красотой. Красота елки равна сумме красот всех висящих на ней игрушек. Так как дети хотят удивить Деда мороза, они хотят как можно красивее украсить ёлку, при этом она не должна упасть.

Вас просят написать программу, которая по заданным параметрам игрушек и ёлки определит максимально возможную красоту наряженной ёлки.

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

Во входном файле содержатся числа M и K — соответственно максимальная масса игрушек на ёлке и количество купленных игрушек. За ними следуют K пар чисел vi ki соответственно вес и красота i-той игрушки.

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

В выходном файле должно содержаться единственное число - максимально возможная красота наряженной ёлки.

Ограничения

1 ≤ K, M ≤ 100 1 ≤ vi, ki ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2
1 2
2 2
4

Задача C. Воздушный замок

Автор:И. Туфанов, И. Олейников
Входной файл: input.txt   Ограничение времени:5 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб

Условие

Накануне нового года Дед Мороз занимается свим привычным делом: он строит воздушные замки. Пространство в котором Дед Мороз строит замки - это куб, который состоит из NxNxN маленьких кубиков. Каждый маленький кубик может быть занят облаком или не занят. Воздушный замок Деда Мороза - это прямоугольный паралеллепипед с целочисленными координатами, стороны которого параллельны осям координат. Кроме того, в пространсте есть M облаков. Дед Мороз не хочет, чтобы его замок задевал облака. Замок задевает облако, если они имеют общую клетку.

Помогите Деду Морозу постоить наибольший по объему замок.

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

Во входном файле содержатся числа N и M. За ними следуют M троек чисел - координаты облаков. Все координаты находятся в пределах между 1 и N включительно. Облака могут занимать одну и ту же клетку.

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

В выходном файле должно содержаться единственное число - объем самого просторного замка.

Ограничения

1 ≤ N ≤ 80 0 ≤ M ≤ 200000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2 1
1 1 2
4
2
3 0
27

Задача D. Новогодняя ёлка-3

Автор:И. Олейников, А Кленин, И Туфанов
Входной файл: input.txt   Ограничение времени:2 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб

Условие

В детском саду города N для празднования Нового Года установили ёлку и для её украшения закупили K елочных игрушек.

Елочные игрушки характеризуются двумя параметрами — массой и красотой. Елка характеризуется тремя параметрами — максимальной массой игрушек, которую она может выдержать, красотой, а также максимальной перегрузкой в одну из сторон (максимальная разница между суммарной массой игрушек на левой и на правой стороне). Красота елки равна сумме красот всех висящих на ней игрушек. Так как дети хотят удивить Деда мороза, они хотят как можно красивее украсить ёлку, при этом она не должна упасть.

Вас просят написать программу, которая по заданным параметрам игрушек и ёлки определит максимально возможную красоту наряженной ёлки.

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

Во входном файле содержатся числа M K Δ — соответственно максимальная масса игрушек на ёлке, количество купленных игрушек и максимальное отклонение. За ними следуют K пар чисел vi ki соответственно вес и красота i-той игрушки.

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

В выходном файле должно содержаться единственное число - максимально возможная красота наряженной ёлки.

Ограничения

1 ≤ К, M ≤ 100 1 ≤ vi, ki ≤ 100 0 ≤ Δ ≤ 20

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2 1
1 2
2 2
4

0.026s 0.003s 13