Как вы знаете, выдры очень любят камешки. Некоторые выдры выбирают себе один камешек на всю жизнь, но Оттервер не из таких. У него есть рюкзак, который вмещает $$$W$$$ килограммов. В его распоряжении есть 3 типа камешков, каждый тип характеризуется своим весом и своей значимостью. Камешки каждого типа он может брать в неограниченном количестве (естественно, взятые камешки должны влезать в рюкзак). Оттервер хочет набрать в рюкзак камешков так, чтобы они имели максимальную суммарную значимость. К сожалению, так как выдры в этой задаче гигантские, то и рюкзак, и камешки соответствующих размеров. Помогите ему с этой сложной задачей, ведь он всего лишь бедный выдр!
В первой строке вводится одно целое число $$$W$$$ — вместимость рюкзака ($$$1 \leqslant W \leqslant 10^9$$$). В следующих трех строках вводится описание типов камешков: пары целых чисел $$$w_i, c_i$$$ — вес камешка и его значимость ($$$1 \leqslant w_i \leqslant 1000$$$, $$$1 \leqslant c_i \leqslant 10^9$$$).
Выведите одно целое число — максимальную суммарную значимость выбранных камешков, которые может взять Оттервер.
203 75 104 8
45
Обратите внимание на ограничение на вес камешка!
