Айоуб думает, что он очень умный человек, поэтому он придумал функцию \(f(s)\), где \(s\) это бинарная строка (строка, содержащая только символы «0» и «1»). Функция \(f(s)\) равна количеству подстрок строки \(s\), которые содержат хотя бы один символ, равный «1».
Более формально, \(f(s)\) равно количеству пар целых чисел \((l, r)\), таких что \(1 \leq l \leq r \leq |s|\) (где \(|s|\) равно длине строки \(s\)), таких что хотя бы один из символов \(s_l, s_{l+1}, \ldots, s_r\) равен «1».
Например, если \(s = \)«01010», то \(f(s) = 12\), потому что есть \(12\) таких пар \((l, r)\): \((1, 2), (1, 3), (1, 4), (1, 5), (2, 2), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 4), (4, 5)\).
Айоуб также думает, что он умнее Махмуда, поэтому дал ему два целых числа \(n\) и \(m\) и следующую задачу. По всем бинарным строкам \(s\) длины \(n\), которые содержат ровно \(m\) символов, равных «1», найдите максимальное значение \(f(s)\).
У Махмуда не получилось решить эту задачу, поэтому он попросил вас о помощи. Можете ли вы помочь ему?
Примечание
В первом тестовом случае, существует только \(3\) строки длины \(3\), которые содержат ровно \(1\) символ, равный «1». Эти строки это: \(s_1 = \)«100», \(s_2 = \)«010», \(s_3 = \)«001». Значения \(f\) для них это: \(f(s_1) = 3, f(s_2) = 4, f(s_3) = 3\), поэтому максимальное значение это \(4\) и ответ равен \(4\).
Во втором тестовом случае, строка \(s\) для которой максимальное значение функции это «101».
Во третьем тестовом случае, строка \(s\) для которой максимальное значение функции это «111».
В четвертом тестовом случае, единственная строка \(s\) длины \(4\), которая содержит ровно \(0\) символов, равных «1» это «0000» и значение функции \(f\) для этой строки это \(0\), поэтому ответ равен \(0\).
В пятом тестовом случае, строка \(s\) с максимальным значением функции это «01010» и она была подробно разобрана в качестве примера в тексте условия задачи.