Рабочее место участника

Тим разрабатывает казуальную RPG для магазина веб-игр iPlay. Чтобы игра не была слишком простой, Тиму нужно определить, насколько сильную армию может собрать игрок для штурма замка главного злодея. Игрок может набрать несколько отрядов, при этом в каждом отряде должны быть войска одного вида, и не может быть более одного отряда с этим видом войск. Максимальное количество отрядов в армии зависит от выбранного в начале игры класса героя (бард, волшебник, паладин и т. д.), а величина отряда – от харизмы героя, максимальная величина которой зависит от действий игрока в процессе игры и класса героя. Виды войск кроме того разделены на 3 типа: регулярные войска (ополченцы, лучники, конница и т. д., которых можно найти в замках), наемники (разбойники, эльфы, кентавры и т. д., которых можно нанять в тавернах) и нежить (привидения, упыри, вампиры и т. д., которых можно найти на кладбищах). Если в армии героя несколько отрядов регулярных войск, то их боевой дух и сила атаки возрастает, но если в армии присутствуют отряды нежити, то сила атаки регулярных войск падает. Количество отрядов наемников не влияет на силу атаки регулярных войск. Для вычисления силы атаки отряда регулярных войск используется формула:

`max(1,\ p*(a+d*(L-N-1)))`,

где `p` – количество юнитов в отряде, `a` – сила атаки одного юнита, `d` – коэффициент влияния боевого духа на атаку, `L` – количество отрядов регулярных войск в армии героя, `N` – количество отрядов нежити в армии героя.

Сила атаки наемников и нежити не зависит от состава других отрядов и вычисляется по формуле: `p*a`.

Максимальное количество юнитов в отряде вычисляется как `|__\ H/u\ __|`, где `H` – харизма героя, а `u` – коэффициент, зависящий от вида войск.

Напишите программу, которая определит максимальную суммарную силу атаки армии.

Первая строка ввода содержит три целых числа: максимальное количество отрядов `K` (`3\ ≤\ K\ ≤\ 10`), харизма героя `H` (`100\ ≤\ H\ ≤\ 10^4`) и количество видов войск `W` (`K\ ≤\ W\ ≤\ 100`). Далее следует `W` строк, каждая строка содержит три целых числа `u_i`, `a_i` и `d_i` – параметры `i`-го вида войск (`1\ ≤\ u_i\ ≤\ 100`, `1\ ≤\ a_i\ ≤\ 1000`, `-1\ ≤\ d_i\ ≤\ a_i`, для регулярных войск `d_i\ >\ 0`, для наемников `d_i\ =\ 0`, для нежити `d_i\ =\ -1`).

В первой строке вывести одно целое число – максимальную суммарную силу атаки армии.

3 100 5
10 10 1
12 20 0
20 20 -1
4 1 1
5 2 -1

350