Равные Суммы Разделов
Разбиение последовательности чисел на группы с равной суммой — это процесс, при котором числа группируются в том же порядке, что и в исходной последовательности, так, чтобы сумма чисел в каждой группе была одинаковой. Например, последовательность:
2 5 1 3 3 7
можно разбить на группы следующим образом:
(2 5) (1 3 3) (7)
так, чтобы сумма каждой группы была равна 7.
Примечание: Разбиение, при котором все числа помещаются в одну группу, также считается разбиением с равной суммой, где сумма равна сумме всех чисел в последовательности.
В этой задаче вам предстоит написать программу, которая принимает на вход последовательность положительных целых чисел и возвращает наименьшую сумму, при которой возможно разбиение последовательности на группы с равной суммой.
Входные данные
Первая строка содержит количество наборов данных p (1 ≤ p ≤ 1000). Первая строка каждого набора данных содержит номер набора данных, за которым следует пробел и десятичное целое число m (1 ≤ m ≤ 10000), обозначающее общее количество целых чисел в последовательности. Последующие строки в наборе данных содержат значения, по 10 чисел в строке, разделенные пробелом. Последняя строка в наборе данных может содержать менее 10 значений.
Выходные данные
Для каждого набора данных выведите одну строку, содержащую номер набора данных в виде десятичного целого числа, пробел и наименьшую сумму для разбиения последовательности на группы с равной суммой.