P5167 xtq’s Magic Brush

When xtq was in fourth grade, he got a set of magical paintbrushes. To test how powerful the brushes were (and to show off his strong artistic talent), he decided to copy several paintings for his art teacher.

The shape of each painting can be abstracted as $n$ cells in a row, where the $i$-th cell has a weight $a_i$. xtq has enough paintbrushes of different colors. Each time he uses one brush, he can paint a continuous segment on the cells with length at least $k$, and then switch to another brush and continue painting starting from the next cell, where $k

The first line contains a positive integer $T$, representing the number of paintings. For each painting: The first line contains two positive integers $n, k$. The second line contains $n$ positive integers $a_1, a_2, a_3, \ldots , a_n$. The third line contains $k$ integers $b_1, b_2, b_3, \ldots , b_k$.

For each painting, output one integer, representing the maximum score xtq can obtain after completing this painting.

Sample explanation: xtq can start from $1$ and gain an initial score of $6$ points. The first segment is $[1,2]$, gaining $5$ points; the second segment is $[3,4]$, gaining $10$ points; the third segment is $[5,6]$, gaining $10$ points. In total, $31$ points. Constraints: For $20\%$ of the testdata, $n\le 10$. For $40\%$ of the testdata, $n\le 3000$. For $70\%$ of the testdata, $n\le 30000$. For $100\%$ of the testdata, $1\le k