В провинции Скайрим, а если быть точнее, в городе Вайтран вполне себе припеваючи поживал придворный маг Фаренгар Тайный Огонь, но недавно началась суматоха с возвращением драконов и появлением драконорождённого, обычные будни...

«Ходят слухи, что драконорождённый уже прибыл в Вайтран, интересно, кто это — может быть высокий или тёмный эльф, у которых есть врождённая способность к магии, а может Бретонец! Нас явно ждут разговоры о рунах и заклинаниях целыми днями...» — думал про себя Фаренгар. Надо ли говорить, как он удивился, когда увидел перед собой орка в тяжёлых доспехах, который с большим трудом разговаривал на человеческом.

Ярл$$$^{\text{∗}}$$$ Вайтрана приказал Фаренгару собрать Драконорождённого в поход и выдать ему магические посохи. Но, как мы знаем, орки не отличаются интеллектом, поэтому каждым выданным Фаренгаром магическим посохом драконорождённый может ударить врага только один раз, после чего посох ломается, а врагу наносится урон, равный длине посоха. У Фаренгара изначально нет посохов, но есть $$$N$$$ заклинаний, $$$i$$$-е из которых может создать посох веса $$$w_i$$$ и длины $$$l_i - c_i \cdot k$$$ для любого неотрицательного $$$k$$$. К сожалению, каждое заклинание с каждым конкретным $$$k$$$ можно использовать не более одного раза. (При этом разные заклинания с одним и тем же $$$k$$$ использовать можно, но каждое не более одного раза.) Фаренгар — сильный маг, он может создать сколько угодно посохов (в рамках описанных ограничений), и даже физика для него не препятствие, он вполне может создавать посохи отрицательной длины, но есть ли в этом смысл...

Всего драконорождённый может нести на себе вес $$$W$$$, поэтому ваша задача помочь Фаренгару собрать драконорождённого в путь, создав ему такие посохи, чтобы он мог нанести суммарно как можно больше урона.

Подзадача 1, 10 баллов: $$$N \leq 400$$$, $$$W \leq 2500$$$.

Подзадача 2, 50 баллов: $$$N \leq 50000$$$.

Подзадача 3, 40 баллов: дополнительных ограничений нет.