K-th Wall Design Strength

You are given three arrays (a, b, c) of length (n) and an integer (r) along with an integer (k). These arrays satisfy (a_i < b_i < c_i) for every (1 \le i \le n). A wall of length (n) meters is built with the following process:

1. First, decide two distinct starting positions (x) and (y) (with (1 \le x < y \le n-r+1)).
2. For each wall, two ranges are chosen: ([x, x+r-1]) and ([y, y+r-1]).
3. For each meter (i) ((1 \le i \le n)), the height is determined as follows: (\bullet) If (i) is not in any chosen range, the height is (a_i). (\bullet) If (i) is in exactly one range, the height is (b_i). (\bullet) If (i) is in both ranges, the height is (c_i).

The strength of the wall is the sum of the heights of its (n) pieces. All possible designs (i.e. all valid pairs ((x,y))) are then sorted in non-decreasing order by their strength. Your task is to output the strength of the (k)-th wall design in this sorted order.

A useful observation is that if we denote (S_{base} = \sum_{i=1}^{n}a_i) and define

[ D(x) = \sum_{i=x}^{x+r-1} (b_i - a_i)]

and the overlap correction term for a design with ranges starting at (x) and (y) (if they overlap, i.e. when (y - x < r)) as

[ O(x,y) = \sum_{i=y}^{x+r-1} (c_i - 2b_i + a_i), \quad \text{for } y - x < r, \quad \text{and } 0 \text{ otherwise}, ]

then the strength (S) of a given design is

[ S = S_{base} + D(x) + D(y) + O(x,y).]

Your program should compute (S) for each valid pair and return the (k)-th smallest value.

inputFormat

The first line contains three integers \(n\), \(r\) and \(k\): the length of the wall, the length of each chosen range, and the design order to be selected.

The next three lines contain \(n\) integers each, representing the arrays \(a\), \(b\), and \(c\) respectively. It is guaranteed that \(a_i < b_i < c_i\) for every \(1 \le i \le n\).

outputFormat

Output a single integer, the strength of the \(k\)-th wall design when all possible designs (formed by choosing two distinct starting positions for the ranges) are sorted in non-decreasing order.

sample

4 2 1
1 2 3 4
2 3 4 5
3 4 5 6

14