У вас есть массив целых чисел \(a_1, a_2, \ldots, a_n\) длины \(n\). В \(i\)-й из следующих \(d\) дней вы собираетесь выполнить ровно одно из следующих двух действий:
- Прибавить \(1\) к каждому из первых \(b_i\) элементов массива \(a\) (т.е. присвоить \(a_j := a_j + 1\) для всех \(1 \le j \le b_i\)).
- Посчитаем количество элементов, которые равны своей позиции (т.е. \(a_j = j\)). Обозначим количество таких элементов за \(c\). Затем нужно прибавить \(c\) к своему счету и сбросить весь массив \(a\) к \(0\)-массиву длины \(n\) (т.е. присвоить \([a_1, a_2, \ldots, a_n] := [0, 0, \ldots, 0]\)).
Изначально ваш счет равен \(0\). Обратите внимание, что в каждый день вы должны выполнить ровно одно из указанных выше действий: нельзя пропустить день или выполнить оба действия в один и тот же день.
Какой максимальный счет вы можете получить в конце?
Поскольку \(d\) может быть довольно большим, последовательность \(b\) дается вам в сжатом виде:
- Вам дана последовательность целых чисел \(v_1, v_2, \ldots, v_k\). Последовательность \(b\) является конкатенацией бесконечного числа копий \(v\): \(b = [v_1, v_2, \ldots, v_k, v_1, v_2, \ldots, v_k, \ldots]\).
Выходные данные
Для каждого набора входных данных выведите одно целое число: максимальный счет, который вы можете получить в конце \(d\)-го дня.
Примечание
В первом наборе входных данных последовательность \(b\) равняется \([1, 3, 2, 3, 1, 3, 2, 3, \ldots]\) и одно из оптимальных решений выглядит следующим образом:
- Выполнить операцию второго типа в \(1\)-й день: счет увеличится на \(3\), а массив \(a\) станет равным \([0, 0, 0]\).
- Выполнить операцию первого типа во \(2\)-й день: массив \(a\) станет равным \([1, 1, 1]\).
- Выполнить операцию первого типа в \(3\)-й день: массив \(a\) станет равным \([2, 2, 1]\).
- Выполнить операцию второго типа в \(4\)-й день: счет увеличится на \(1\), а массив \(a\) станет равным \([0, 0, 0]\).
Можно показать, что набрать больше \(4\) невозможно, поэтому ответ — \(4\).
Во втором наборе входных данных последовательность \(b\) равняется \([6, 6, 6, 6, \ldots]\). Один из способов набрать \(3\) — это выполнить операции первого типа в \(1\)-й и \(3\)-й дни и выполнить операцию второго типа во \(2\)-й день.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 4 4
1 2 3
1 3 2 3
6 2 3
6 1 2 4 1 5
6 6
5 1 1
0 5 0 5 0
5
1 1 1
1
1
3 4 6
1 2 3
1 3 2 3
|
4
3
0
1
5
|