Это простая версия задачи. Она отличается от сложной только ограничениями на \(n\) и \(t\).
Есть колода из \(n\) карт, каждая из которых характеризуется своей силой. Бывают карты двух видов:
- карта героя, сила такой карты всегда равна \(0\);
- карта бонуса, сила такой карты всегда положительна.
Вы можете делать с колодой следующее:
- взять карту сверху колоды;
- если эта карта является картой бонуса, вы можете положить её на верх своей колоды с бонусами либо в сброс;
- если эта карта является картой героя, то к его силе прибавляется сила верхней карты из вашей колоды с бонусами (если она не пуста), после этого герой добавляется к вашей армии, а использованный бонус уходит в сброс.
Ваша задача с помощью таких действий собрать армию с наибольшей суммарной силой.
Выходные данные
Выведите \(t\) чисел, каждое из которых является ответом на соответствующий набор входных данных — максимальную возможную суммарную силу армии, которой можно добиться.
Примечание
В первом примере можно взять бонусы \(1\) и \(2\). Обе карты героев получат по \(3\) к силе. Если взять все бонусы, один из них останется неиспользованным.
Во втором примере карту героя сверху колоды невозможно усилить, а остальных можно усилить бонусами \(2\) и \(3\) и получить \(6\) суммарной силы.
В четвёртом примере можно взять бонусы \(1\), \(2\), \(3\), \(5\) и пропустить бонус \(6\), тогда герой \(4\) будет усилен бонусом \(3\) на \(5\), а герой \(7\) бонусом \(5\) на \(4\). \(4+5=9\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5
3 3 3 0 0
6
0 3 3 0 0 3
7
1 2 3 0 4 5 0
7
1 2 5 0 4 3 0
5
3 1 0 0 4
|
6
6
8
9
4
|