Maximum Monogonosity (Codeforces 1859E)
Tags: Math, brute force

You are given an array $$$a$$$ of length $$$n$$$ and an array $$$b$$$ of length $$$n$$$. The cost of a segment $$$[l, r]$$$, $$$1 \le l \le r \le n$$$, is defined as $$$|b_l - a_r| + |b_r - a_l|$$$.Recall that two segments $$$[l_1, r_1]$$$, $$$1 \le l_1 \le r_1 \le n$$$, and $$$[l_2, r_2]$$$, $$$1 \le l_2 \le r_2 \le n$$$, are non-intersecting if one of the following conditions is satisfied: $$$r_1 < l_2$$$ or $$$r_2 < l_1$$$.The length of a segment $$$[l, r]$$$, $$$1 \le l \le r \le n$$$, is defined as $$$r - l + 1$$$.Find the maximum possible sum of costs of non-intersecting segments $$$[l_j, r_j]$$$, $$$1 \le l_j \le r_j \le n$$$, whose total length is equal to $$$k$$$.

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \le t \le 1000)$$$ — the number of sets of input data. The description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 3000$$$) — the length of array $$$a$$$ and the total length of segments.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the elements of array $$$a$$$.The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$-10^9 \le b_i \le 10^9$$$) — the elements of array $$$b$$$.It is guaranteed that the sum of $$$n$$$ over all test case does not exceed $$$3000$$$.

Output: For each test case, output a single number — the maximum possible sum of costs of such segments.

Note: In the first test case, the cost of any segment is $$$0$$$, so the total cost is $$$0$$$.In the second test case, we can take the segment $$$[1, 1]$$$ with a cost of $$$8$$$ and the segment $$$[3, 3]$$$ with a cost of $$$2$$$ to get a total sum of $$$10$$$. It can be shown that this is the optimal solution.In the third test case, we are only interested in segments of length $$$1$$$, and the cost of any such segment is $$$0$$$.In the fourth test case, it can be shown that the optimal sum is $$$16$$$. For example, we can take the segments $$$[3, 3]$$$ and $$$[4, 4]$$$.

Sample Inputs:
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

Sample Outputs:
0
10
0
16
28

Solution (Python):
from sys import stdin, stdout
t = int(stdin.readline())
for _ in range(t):
    (n, k) = [int(x) for x in stdin.readline().split()]
    a = [int(x) for x in stdin.readline().split()]
    b = [int(x) for x in stdin.readline().split()]
    dp = [0] * (k + 1)
    for i in range(n, k - 1, -1):
        dp2 = [0]
        diag11 = a[i - 1] + b[i - 1]
        diag12 = a[i - 1] - b[i - 1]
        diag21 = -a[i - 1] + b[i - 1]
        diag22 = -a[i - 1] - b[i - 1]
        for j in range(1, k + 1):
            dp2.append(max(diag11 - b[i - j] - a[i - j], diag12 - b[i - j] + a[i - j], diag21 + b[i - j] - a[i - j], diag22 + b[i - j] + a[i - j], dp[j]))
            if i - j > 0:
                diag11 = max(diag11, dp2[-1] + a[i - j - 1] + b[i - j - 1])
                diag12 = max(diag12, dp2[-1] + a[i - j - 1] - b[i - j - 1])
                diag21 = max(diag21, dp2[-1] - a[i - j - 1] + b[i - j - 1])
                diag22 = max(diag22, dp2[-1] - a[i - j - 1] - b[i - j - 1])
        dp = dp2
    stdout.write(str(dp[-1]) + '\n')

Solution (Python):
from math import gcd
from math import sqrt
from bisect import bisect_left
from operator import itemgetter
from bisect import bisect_right
from operator import itemgetter
import itertools
import random

class DETAILS:

    def slovar():
        slov = {}
        if 0 in slov:
            slov[0] = slov.get(0) + 1
        else:
            slov[0] = 1
        slov[-1] = -1
        slov1 = dict(sorted(slov.items()))
        slov2 = dict(sorted(slov.items(), key=itemgetter(1)))
        return (slov, slov1, slov2)

    def perestanovki(mas):
        permutations = list(itertools.permutations(mas))
        return permutations

    def kombinations(mas1, mas2):
        products = list(itertools.product(x, y))
        return products

    def randomizn(n):
        x = random.randint(0, n)
        return x

    def shuf(mas):
        random.shuffle(mas)
        return mas

    def SS(number, from_base, to_base, upper=False):
        number = int(str(number), from_base)
        digits = '0123456789abcdefghijklmnopqrstuvwxyz'
        if to_base > len(digits):
            return None
        result = ''
        while number > 0:
            result = digits[number % to_base] + result
            number //= to_base
        return result.upper() if upper else result

    def prefsu(mas):
        new = []
        su = 0
        for i in range(len(mas)):
            su += mas[i]
            new += [su]
        return new

    def Fast_power(a, n, mod):
        ans = 1
        while n > 0:
            if n & 1:
                ans = ans * a % mod
            a = a * a % mod
            n >>= 1
        return ans

class BINP:

    def vst_left(elem, mas):
        ind = bisect_left(mas, elem)
        mas = mas[:ind] + [elem] + mas[ind:]
        return mas

    def vst_right(elem, mas):
        ind = bisect_right(mas, elem)
        mas = mas[:ind] + [elem] + mas[ind:]
        return mas

    def left(elem, mas):
        ind = bisect_left(mas, elem)
        return ind

    def right(elem, mas):
        ind = bisect_right(mas, elem)
        return ind

class MATH:

    def nod(a, b):
        return gcd(a, b)

    def nok(a, b):
        return a * b // gcd(a, b)

    def fact(n):
        if n == 1:
            return 1
        return fact(n - 1) * n

    def kol_del(n):
        k = 0
        if int(n ** 0.5) ** 2 == n:
            k -= 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                k += 2
        return k

    def prost(n):
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                return False
        return True

    def allprimes(n):
        primes = [i for i in range(n + 1)]
        primes[1] = 0
        i = 2
        while i <= n:
            if primes[i] != 0:
                j = i + i
                while j <= n:
                    primes[j] = 0
                    j = j + i
            i += 1
        primes = [i for i in primes if i != 0]
        return primes

class GRAPH:

    def matsme(mas):
        ma = -10 ** 18
        for el in mas:
            ma = max(ma, el[0], el[1])
        S = [[] for i in range(ma)]
        for el in mas:
            a = el[0] - 1
            b = el[1] - 1
            S[a] += [b]
            S[b] += [a]
        return S

    def bfs(graph, v):
        v -= 1
        vis = [-1] * len(graph)
        vis[v] = 0
        mas1 = [v]
        mas2 = []
        while len(mas1) > 0:
            for el in mas1:
                for i in range(len(graph[el])):
                    new_v = graph[el][i]
                    if vis[new_v] == -1:
                        mas2 += [new_v]
                        vis[new_v] = 0
            mas1 = mas2
            mas2 = []

    def dfs(graph, v):
        v -= 1
        vis = [-1] * len(graph)
        GRAPH.realdfs(graph, v, vis)

    def realdfs(graph, v, vis):
        vis[v] = 0
        for i in range(len(graph[el])):
            new_v = graph[el][i]
            if vis[new_v] == -1:
                GRAPH.realdfs(graph, v, vis)

    def matsmede(mas):
        ma = -10 ** 18
        for el in mas:
            ma = max(ma, el[0], el[1])
        S = [[] for i in range(ma)]
        for el in mas:
            a = el[0] - 1
            b = el[1] - 1
            c = el[2]
            S[a] += [[b, c]]
            S[b] += [[a, c]]
        return S

    def Deikstra(graphpair, start, finish):
        start -= 1
        finish -= 1
        n = len(graphpair)
        INF = 10 ** 18
        cur = start
        dist = [INF] * n
        dist[cur] = 0
        diiist = [INF] * n
        diiist[cur] = 0
        pred = [0] * n
        while cur != finish and dist[cur] != INF:
            mas = graphpair[cur]
            for i in range(len(mas)):
                dist[mas[i][0]] = min(dist[mas[i][0]], dist[cur] + mas[i][1])
                if min(dist[mas[i][0]], dist[cur] + mas[i][1]) == dist[cur] + mas[i][1]:
                    pred[mas[i][0]] = cur
                diiist[mas[i][0]] = min(diiist[mas[i][0]], diiist[cur] + mas[i][1])
            diiist[cur] = INF
            cur = diiist.index(min(diiist))
        i = finish
        ans = []
        while i != start:
            ans += [i + 1]
            i = pred[i]
        ans += [i + 1]
        ans.reverse()
        return (dist[finish], ans)

    def kol_komponent(graph):
        n = len(graph)
        vis = [-1] * n
        ans = 0
        for i in range(n):
            if vis[i] == -1:
                ans += 1
                v = i
                mas1 = [v]
                mas2 = []
                while len(mas1) > 0:
                    for el in mas1:
                        for i in range(len(graph[el])):
                            new_v = graph[el][i]
                            if vis[new_v] == -1:
                                mas2 += [new_v]
                                vis[new_v] = 0
                    mas1 = mas2
                    mas2 = []
        return ans

class FEN:

    def Fenwikstart(mas):
        n = len(mas)
        Fenwiksum = [0] * n
        for i in range(len(mas)):
            ind1 = i & i + 1
            ind2 = i
            Fenwiksum[i] = sum(mas[ind1:ind2 + 1])
        return Fenwiksum

    def Fenwiksum(Fsum, l, r):
        su1 = 0
        while r >= 0:
            su1 += Fsum[r]
            r = (r & r + 1) - 1
        su2 = 0
        l -= 1
        while l >= 0:
            su2 += Fsum[l]
            l = (l & l + 1) - 1
        return su1 - su2

    def Fenwikizm(Fsum, mas, ind, x):
        razn = x - mas[ind]
        n = len(Fsum)
        while ind < n:
            Fsum[ind] += razn
            ind = ind | ind + 1
        return Fsum

class DO:

    def DOstart(mas):
        l = len(mas)
        k = 1
        while k < l:
            k = k * 2
        mas = mas + [0] * (k - l)
        n = len(mas)
        Der = [-1] * (2 * n)
        v = 0
        for i in range(n, n * 2):
            Der[i] = mas[v]
            v += 1
        for i in range(n - 1, 0, -1):
            Der[i] = Der[i * 2] + Der[i * 2 + 1]
        return (Der, mas)

    def DOsum(do, v, tl, tr, l, r):
        if l > r:
            return 0
        if l == tl and r == tr:
            return do[v]
        tm = (tl + tr) // 2
        return DO.DOsum(do, v * 2, tl, tm, l, min(r, tm)) + DO.DOsum(do, v * 2 + 1, tm + 1, tr, max(l, tm + 1), r)

    def DOizm(do, ind, x):
        el = do[len(do) // 2 + ind]
        razn = x - el
        ind = ind + len(do) // 2
        do[ind] += razn
        while ind > 1:
            ind = ind // 2
            do[ind] += razn
        return do

class DOMIN:

    def DOminstart(mas):
        l = len(mas)
        k = 1
        while k < l:
            k = k * 2
        mas = mas + [10 ** 18] * (k - l)
        n = len(mas)
        Der = [-1] * (2 * n)
        v = 0
        for i in range(n, n * 2):
            Der[i] = mas[v]
            v += 1
        for i in range(n - 1, 0, -1):
            Der[i] = min(Der[i * 2], Der[i * 2 + 1])
        return (Der, mas)

    def DOmin(do, v, tl, tr, l, r):
        if l > r:
            return 0
        if l == tl and r == tr:
            return do[v]
        tm = (tl + tr) // 2
        return min(DO.DOsum(do, v * 2, tl, tm, l, min(r, tm)), DO.DOsum(do, v * 2 + 1, tm + 1, tr, max(l, tm + 1), r))

    def DOminizm(do, ind, x):
        ind = ind + len(do) // 2
        do[ind] = x
        while ind > 1:
            p = ind // 2
            do[p] = min(do[p * 2], do[p * 2 + 1])
            ind = ind // 2
        return do

class DOMAX:

    def DOmaxstart(mas):
        l = len(mas)
        k = 1
        while k < l:
            k = k * 2
        mas = mas + [-10 ** 18] * (k - l)
        n = len(mas)
        Der = [-1] * (2 * n)
        v = 0
        for i in range(n, n * 2):
            Der[i] = mas[v]
            v += 1
        for i in range(n - 1, 0, -1):
            Der[i] = max(Der[i * 2], Der[i * 2 + 1])
        return (Der, mas)

    def DOmax(do, v, tl, tr, l, r):
        if l > r:
            return 0
        if l == tl and r == tr:
            return do[v]
        tm = (tl + tr) // 2
        return max(DO.DOsum(do, v * 2, tl, tm, l, min(r, tm)), DO.DOsum(do, v * 2 + 1, tm + 1, tr, max(l, tm + 1), r))

    def DOmaxizm(do, ind, x):
        ind = ind + len(do) // 2
        do[ind] = x
        while ind > 1:
            p = ind // 2
            do[p] = max(do[p * 2], do[p * 2 + 1])
            ind = ind // 2
        return do
t = int(input())
for test in range(t):
    (n, k) = map(int, input().split())
    (*a,) = map(int, input().split())
    (*b,) = map(int, input().split())
    dp = [[-10 ** 18] * 5 for i in range(k + 1)]
    dp[0][0] = 0
    for s in range(n):
        for i in range(min(s + 1, k), 0, -1):
            dp[i][1] = dp[i - 1][1]
            dp[i][2] = dp[i - 1][2]
            dp[i][3] = dp[i - 1][3]
            dp[i][4] = dp[i - 1][4]
        for i in range(min(s + 1, k)):
            dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + a[s] + b[s])
            dp[i + 1][2] = max(dp[i + 1][2], dp[i][0] - a[s] + b[s])
            dp[i + 1][3] = max(dp[i + 1][3], dp[i][0] + a[s] - b[s])
            dp[i + 1][4] = max(dp[i + 1][4], dp[i][0] - a[s] - b[s])
        for i in range(min(s + 1, k) + 1):
            dp[i][0] = max(dp[i][0], dp[i][1] - a[s] - b[s])
            dp[i][0] = max(dp[i][0], dp[i][2] - a[s] + b[s])
            dp[i][0] = max(dp[i][0], dp[i][3] + a[s] - b[s])
            dp[i][0] = max(dp[i][0], dp[i][4] + a[s] + b[s])
    print(dp[k][0])

Solution (Python):
from math import gcd
from math import sqrt
from bisect import bisect_left
from operator import itemgetter
from bisect import bisect_right
from operator import itemgetter
import itertools
import random

class DETAILS:

    def slovar():
        slov = {}
        if 0 in slov:
            slov[0] = slov.get(0) + 1
        else:
            slov[0] = 1
        slov[-1] = -1
        slov1 = dict(sorted(slov.items()))
        slov2 = dict(sorted(slov.items(), key=itemgetter(1)))
        return (slov, slov1, slov2)

    def perestanovki(mas):
        permutations = list(itertools.permutations(mas))
        return permutations

    def kombinations(mas1, mas2):
        products = list(itertools.product(x, y))
        return products

    def randomizn(n):
        x = random.randint(0, n)
        return x

    def shuf(mas):
        random.shuffle(mas)
        return mas

    def SS(number, from_base, to_base, upper=False):
        number = int(str(number), from_base)
        digits = '0123456789abcdefghijklmnopqrstuvwxyz'
        if to_base > len(digits):
            return None
        result = ''
        while number > 0:
            result = digits[number % to_base] + result
            number //= to_base
        return result.upper() if upper else result

    def prefsu(mas):
        new = []
        su = 0
        for i in range(len(mas)):
            su += mas[i]
            new += [su]
        return new

    def Fast_power(a, n, mod):
        ans = 1
        while n > 0:
            if n & 1:
                ans = ans * a % mod
            a = a * a % mod
            n >>= 1
        return ans

class BINP:

    def vst_left(elem, mas):
        ind = bisect_left(mas, elem)
        mas = mas[:ind] + [elem] + mas[ind:]
        return mas

    def vst_right(elem, mas):
        ind = bisect_right(mas, elem)
        mas = mas[:ind] + [elem] + mas[ind:]
        return mas

    def left(elem, mas):
        ind = bisect_left(mas, elem)
        return ind

    def right(elem, mas):
        ind = bisect_right(mas, elem)
        return ind

class MATH:

    def nod(a, b):
        return gcd(a, b)

    def nok(a, b):
        return a * b // gcd(a, b)

    def fact(n):
        if n == 1:
            return 1
        return fact(n - 1) * n

    def kol_del(n):
        k = 0
        if int(n ** 0.5) ** 2 == n:
            k -= 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                k += 2
        return k

    def prost(n):
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                return False
        return True

    def allprimes(n):
        primes = [i for i in range(n + 1)]
        primes[1] = 0
        i = 2
        while i <= n:
            if primes[i] != 0:
                j = i + i
                while j <= n:
                    primes[j] = 0
                    j = j + i
            i += 1
        primes = [i for i in primes if i != 0]
        return primes

class GRAPH:

    def matsme(mas):
        ma = -10 ** 18
        for el in mas:
            ma = max(ma, el[0], el[1])
        S = [[] for i in range(ma)]
        for el in mas:
            a = el[0] - 1
            b = el[1] - 1
            S[a] += [b]
            S[b] += [a]
        return S

    def bfs(graph, v):
        v -= 1
        vis = [-1] * len(graph)
        vis[v] = 0
        mas1 = [v]
        mas2 = []
        while len(mas1) > 0:
            for el in mas1:
                for i in range(len(graph[el])):
                    new_v = graph[el][i]
                    if vis[new_v] == -1:
                        mas2 += [new_v]
                        vis[new_v] = 0
            mas1 = mas2
            mas2 = []

    def dfs(graph, v):
        v -= 1
        vis = [-1] * len(graph)
        GRAPH.realdfs(graph, v, vis)

    def realdfs(graph, v, vis):
        vis[v] = 0
        for i in range(len(graph[el])):
            new_v = graph[el][i]
            if vis[new_v] == -1:
                GRAPH.realdfs(graph, v, vis)

    def matsmede(mas):
        ma = -10 ** 18
        for el in mas:
            ma = max(ma, el[0], el[1])
        S = [[] for i in range(ma)]
        for el in mas:
            a = el[0] - 1
            b = el[1] - 1
            c = el[2]
            S[a] += [[b, c]]
            S[b] += [[a, c]]
        return S

    def Deikstra(graphpair, start, finish):
        start -= 1
        finish -= 1
        n = len(graphpair)
        INF = 10 ** 18
        cur = start
        dist = [INF] * n
        dist[cur] = 0
        diiist = [INF] * n
        diiist[cur] = 0
        pred = [0] * n
        while cur != finish and dist[cur] != INF:
            mas = graphpair[cur]
            for i in range(len(mas)):
                dist[mas[i][0]] = min(dist[mas[i][0]], dist[cur] + mas[i][1])
                if min(dist[mas[i][0]], dist[cur] + mas[i][1]) == dist[cur] + mas[i][1]:
                    pred[mas[i][0]] = cur
                diiist[mas[i][0]] = min(diiist[mas[i][0]], diiist[cur] + mas[i][1])
            diiist[cur] = INF
            cur = diiist.index(min(diiist))
        i = finish
        ans = []
        while i != start:
            ans += [i + 1]
            i = pred[i]
        ans += [i + 1]
        ans.reverse()
        return (dist[finish], ans)

    def kol_komponent(graph):
        n = len(graph)
        vis = [-1] * n
        ans = 0
        for i in range(n):
            if vis[i] == -1:
                ans += 1
                v = i
                mas1 = [v]
                mas2 = []
                while len(mas1) > 0:
                    for el in mas1:
                        for i in range(len(graph[el])):
                            new_v = graph[el][i]
                            if vis[new_v] == -1:
                                mas2 += [new_v]
                                vis[new_v] = 0
                    mas1 = mas2
                    mas2 = []
        return ans

class FEN:

    def Fenwikstart(mas):
        n = len(mas)
        Fenwiksum = [0] * n
        for i in range(len(mas)):
            ind1 = i & i + 1
            ind2 = i
            Fenwiksum[i] = sum(mas[ind1:ind2 + 1])
        return Fenwiksum

    def Fenwiksum(Fsum, l, r):
        su1 = 0
        while r >= 0:
            su1 += Fsum[r]
            r = (r & r + 1) - 1
        su2 = 0
        l -= 1
        while l >= 0:
            su2 += Fsum[l]
            l = (l & l + 1) - 1
        return su1 - su2

    def Fenwikizm(Fsum, mas, ind, x):
        razn = x - mas[ind]
        n = len(Fsum)
        while ind < n:
            Fsum[ind] += razn
            ind = ind | ind + 1
        return Fsum

class DO:

    def DOstart(mas):
        l = len(mas)
        k = 1
        while k < l:
            k = k * 2
        mas = mas + [0] * (k - l)
        n = len(mas)
        Der = [-1] * (2 * n)
        v = 0
        for i in range(n, n * 2):
            Der[i] = mas[v]
            v += 1
        for i in range(n - 1, 0, -1):
            Der[i] = Der[i * 2] + Der[i * 2 + 1]
        return (Der, mas)

    def DOsum(do, v, tl, tr, l, r):
        if l > r:
            return 0
        if l == tl and r == tr:
            return do[v]
        tm = (tl + tr) // 2
        return DO.DOsum(do, v * 2, tl, tm, l, min(r, tm)) + DO.DOsum(do, v * 2 + 1, tm + 1, tr, max(l, tm + 1), r)

    def DOizm(do, ind, x):
        el = do[len(do) // 2 + ind]
        razn = x - el
        ind = ind + len(do) // 2
        do[ind] += razn
        while ind > 1:
            ind = ind // 2
            do[ind] += razn
        return do

class DOMIN:

    def DOminstart(mas):
        l = len(mas)
        k = 1
        while k < l:
            k = k * 2
        mas = mas + [10 ** 18] * (k - l)
        n = len(mas)
        Der = [-1] * (2 * n)
        v = 0
        for i in range(n, n * 2):
            Der[i] = mas[v]
            v += 1
        for i in range(n - 1, 0, -1):
            Der[i] = min(Der[i * 2], Der[i * 2 + 1])
        return (Der, mas)

    def DOmin(do, v, tl, tr, l, r):
        if l > r:
            return 0
        if l == tl and r == tr:
            return do[v]
        tm = (tl + tr) // 2
        return min(DO.DOsum(do, v * 2, tl, tm, l, min(r, tm)), DO.DOsum(do, v * 2 + 1, tm + 1, tr, max(l, tm + 1), r))

    def DOminizm(do, ind, x):
        ind = ind + len(do) // 2
        do[ind] = x
        while ind > 1:
            p = ind // 2
            do[p] = min(do[p * 2], do[p * 2 + 1])
            ind = ind // 2
        return do

class DOMAX:

    def DOmaxstart(mas):
        l = len(mas)
        k = 1
        while k < l:
            k = k * 2
        mas = mas + [-10 ** 18] * (k - l)
        n = len(mas)
        Der = [-1] * (2 * n)
        v = 0
        for i in range(n, n * 2):
            Der[i] = mas[v]
            v += 1
        for i in range(n - 1, 0, -1):
            Der[i] = max(Der[i * 2], Der[i * 2 + 1])
        return (Der, mas)

    def DOmax(do, v, tl, tr, l, r):
        if l > r:
            return 0
        if l == tl and r == tr:
            return do[v]
        tm = (tl + tr) // 2
        return max(DO.DOsum(do, v * 2, tl, tm, l, min(r, tm)), DO.DOsum(do, v * 2 + 1, tm + 1, tr, max(l, tm + 1), r))

    def DOmaxizm(do, ind, x):
        ind = ind + len(do) // 2
        do[ind] = x
        while ind > 1:
            p = ind // 2
            do[p] = max(do[p * 2], do[p * 2 + 1])
            ind = ind // 2
        return do
t = int(input())
for test in range(t):
    (n, k) = map(int, input().split())
    (*a,) = map(int, input().split())
    (*b,) = map(int, input().split())
    dp = [[-10 ** 18] * 5 for i in range(k + 1)]
    dp[0][0] = 0
    for s in range(n):
        for i in range(min(s + 1, k), 0, -1):
            dp[i][1] = dp[i - 1][1]
            dp[i][2] = dp[i - 1][2]
            dp[i][3] = dp[i - 1][3]
            dp[i][4] = dp[i - 1][4]
        for i in range(min(s + 1, k)):
            dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + a[s] + b[s])
            dp[i + 1][2] = max(dp[i + 1][2], dp[i][0] - a[s] + b[s])
            dp[i + 1][3] = max(dp[i + 1][3], dp[i][0] + a[s] - b[s])
            dp[i + 1][4] = max(dp[i + 1][4], dp[i][0] - a[s] - b[s])
        for i in range(min(s + 1, k) + 1):
            dp[i][0] = max(dp[i][0], dp[i][1] - a[s] - b[s])
            dp[i][0] = max(dp[i][0], dp[i][2] - a[s] + b[s])
            dp[i][0] = max(dp[i][0], dp[i][3] + a[s] - b[s])
            dp[i][0] = max(dp[i][0], dp[i][4] + a[s] + b[s])
    print(dp[k][0])