C. Приключения Алисы в нарезании торта
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса на чаепитии у Безумного Шляпника! Есть длинный прямоугольный торт, состоящий из $$$n$$$ секций с вкусностями $$$a_1, a_2, \ldots, a_n$$$. На чаепитии присутствуют $$$m$$$ существ, не считая Алисы.

Алиса нарежет торт на $$$m + 1$$$ кусочков. Формально, она разделит торт на $$$m + 1$$$ подмассивов, где каждый подмассив состоит из некоторого количества смежных секций. Вкусность кусочка равна сумме вкусностей секций в нем. После этого она распределит эти $$$m + 1$$$ кусочков между $$$m$$$ существами и собой (её кусок может быть пустым). Однако каждое из $$$m$$$ существ будет довольно только в случае, если вкусность его кусочка будет $$$v$$$ или больше.

Алиса хочет, чтобы каждое существо было довольно. При этом условии она хочет максимизировать вкусность своего собственного куска. Можете ли вы помочь Алисе найти максимальную вкусность, которую может иметь её кусок? Если нет способа сделать так, чтобы каждое существо было довольно, выведите $$$-1$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n, m, v$$$ ($$$1\le m\le n\le 2\cdot 10^5$$$; $$$1\le v\le 10^9$$$) — количество секций, количество существ и минимальные требования существ к вкусу.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — вкусности секций.

Сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите максимальную вкусность, которую Алиса может достичь для своего куска, или $$$-1$$$, если нет способа сделать так, чтобы каждое существо было довольно.

Пример
Входные данные
7
6 2 1
1 1 10 1 1 10
6 2 2
1 1 10 1 1 10
6 2 3
1 1 10 1 1 10
6 2 10
1 1 10 1 1 10
6 2 11
1 1 10 1 1 10
6 2 12
1 1 10 1 1 10
6 2 12
1 1 1 1 10 10
Выходные данные
22
12
2
2
2
0
-1
Примечание

Для первого набора входных данных Алиса может отдать первую и вторую секции как отдельные куски, а затем взять оставшиеся секции общей вкусностью $$$10 + 1 + 1 + 10 = 22$$$ себе. Мы можем показать, что лучше она сделать не может.

Для второго набора входных данных Алиса может отдать первую и вторую секции как один кусок, а шестую секцию как один кусок. Она может затем взять секции общей стоимостью $$$10 + 1 + 1 = 12$$$ вкусностью себе. Мы можем показать, что лучше она сделать не может.

Для седьмого набора входных данных Алиса не может дать каждому существу кусок вкусностью не менее $$$12$$$.