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