У Монокарпа была последовательность \(a\), состоящая из \(n + m\) целых чисел \(a_1, a_2, \dots, a_{n + m}\). Он раскрасил элементы в два цвета: красный и синий; \(n\) элементов были окрашены в красный цвет, все остальные \(m\) элементов были окрашены в синий.
После покраски элементов он выписал две последовательности \(r_1, r_2, \dots, r_n\) и \(b_1, b_2, \dots, b_m\). Последовательность \(r\) состояла из всех красных элементов \(a\) в порядке их появления в \(a\); аналогично, последовательность \(b\) состояла из всех синих элементов \(a\) также в порядке их появления в \(a\).
К сожалению, исходная последовательность была утеряна, и у Монокарпа остались только последовательности \(r\) и \(b\). Он хочет восстановить исходную последовательность. В случае, если существует несколько способов его восстановления, он хочет выбрать способ восстановления, который максимизирует значение
\(\)f(a) = \max(0, a_1, (a_1 + a_2), (a_1 + a_2 + a_3), \dots, (a_1 + a_2 + a_3 + \dots + a_{n + m}))\(\)
Помогите Монокарпу вычислить максимально возможное значение \(f(a)\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимально возможное значение \(f(a)\).
Примечание
В пояснениях к примерам красные элементы выделены жирным шрифтом.
В первом примере одной из возможных последовательностей \(a\) является \([\mathbf{6}, 2, \mathbf{-5}, 3, \mathbf{7}, \mathbf{-3}, -4]\).
Во втором примере одна из возможных последовательностей \(a\) равна \([10, \mathbf{1}, -3, \mathbf{1}, 2, 2]\).
В третьем примере одной из возможных последовательностей \(a\) является \([\mathbf{-1}, -1, -2, -3, \mathbf{-2}, -4, -5, \mathbf{-3}, \mathbf{-4}, \mathbf{-5}]\).
В четвертом примере одной из возможных последовательностей \(a\) является \([0, \mathbf{0}]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
6 -5 7 -3
3
2 3 -4
2
1 1
4
10 -3 2 2
5
-1 -2 -3 -4 -5
5
-1 -2 -3 -4 -5
1
0
1
0
|
13
13
0
0
|