Вам дан массив \(a\) длины \(n\) и массив \(b\) длины \(n\). Назовем стоимостью отрезка \([l, r]\), \(1 \le l \le r \le n\), значение \(|b_l - a_r| + |b_r - a_l|\).
Напомним, что два отрезка \([l_1, r_1]\), \(1 \le l_1 \le r_1 \le n\), и \([l_2, r_2]\), \(1 \le l_2 \le r_2 \le n\), являются непересекающимися, если выполнено одно из двух условий: \(r_1 < l_2\) или \(r_2 < l_1\).
Также длиной отрезка \([l, r]\), \(1 \le l \le r \le n\), мы называем значение \(r - l + 1\).
Найдите максимально возможную суммарную стоимость попарно непересекающихся отрезков \([l_j, r_j]\), \(1 \le l_j \le r_j \le n\), суммарная длина которых равна \(k\).
Выходные данные
Для каждого набора входных данных выведите одно число — максимально возможную суммарную стоимость таких отрезков.
Примечание
В первом наборе входных данных стоимость любого отрезка равна \(0\), поэтому суммарная стоимость равна \(0\).
Во втором наборе входных данных можно взять отрезок \([1, 1]\) со стоимостью \(8\) и отрезок \([3, 3]\) со стоимостью \(2\), чтобы получить сумму \(10\). Можно показать, что это оптимальное решение.
В третьем наборе входных данных нас интересуют только отрезки длины \(1\), а стоимость любого такого отрезка равна \(0\).
В четвертом наборе входных данных можно показать, что оптимальная сумма равна \(16\). Например, можно взять отрезки \([3, 3]\) и \([4, 4]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4 4
1 1 1 1
1 1 1 1
3 2
1 3 2
5 2 3
5 1
1 2 3 4 5
1 2 3 4 5
7 2
1 3 7 6 4 7 2
1 5 3 2 7 4 5
4 2
17 3 5 8
16 2 5 9
|
0
10
0
16
28
|