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

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

Условие

В детском саду города 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.034s 0.008s 15