Отряд из \(n\) воинов защищает замок от нападения дракона. Между драконом и замком есть \(m\) баррикад.
Воины пронумерованы от \(1\) до \(n\). \(i\)-й воин знает \(k_i\) атак: \(j\)-я из них наносит \(a_{i,j}\) урона дракону и может быть применена только есть между замком и драконом ровно \(b_{i,j}\) баррикад.
Воины ходят один за другим, начиная с воина \(1\). После того как воин \(n\) завершит свой ход, считается суммарный урон, нанесенный дракону. \(i\)-й воин в свой ход совершает одно из трех возможных действий:
- разрушить одну баррикаду (если еще остались);
- применить одну из \(k_i\) своих атак;
- пропустить ход.
Суммарный урон считается, как сумма уронов от атак, примененных воинами, которые в свой ход выбрали атаковать. Какой наибольший суммарный урон воины могут нанести дракону?
Выходные данные
Выведите одно целое число — наибольший суммарный урон, который воины могут нанести дракону.
Примечание
В первом примере лучший выбор следующий:
- воин \(1\) уничтожает баррикаду, остается \(3\) баррикады;
- воин \(2\) применяет свою первую атаку (он может это сделать, потому что \(b_{1,1}=3\), что равно текущему числу баррикад).
Суммарный урон равен \(10\).
Если бы первый воин применил свою атаку или пропустил свой ход, то второй мог бы применить только вторую атаку. Таким образом, урон был бы \(2+5=7\) или \(5\).
Во втором примере первый воин пропускает свой ход, второй воин пропускает свой ход, а третий воин применяет свою единственную атаку.
В третьем примере есть два варианта:
- оба воина применяют свои вторые атаки;
- первый воин уничтожает одну баррикаду, а второй воин применяет свою первую атаку.
В обоих случаях получается \(30\) суммарного урона.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 4
1
2
4
2
10 5
3 4
|
10
|
|
2
|
3 3
1
1
0
1
20
2
1
100
3
|
100
|
|
3
|
2 1
2
10 10
0 1
2
30 20
0 1
|
30
|