提示: 欢迎访问OurACM平台。
Problem 2060 The Sum of Sub-matrices

Accept: 40    Submit: 135
Time Limit: 1500 mSec    Memory Limit : 32768 KB

Problem Description

Seen draw a big 3*n matrix , whose entries Ai,j are all integer numbers ( 1 <= i <= 3, 1 <= j <= n ). Now he selects k sub-matrices( each Aij only belong one sub-matrices ), hoping to find the largest sum of sub-matrices’ elements.

Input

There are multiple test cases.

For each test case, the first line contains an integer n, k (1 <= n <= 100, 1 <= k <= 5, 3 * n >= k). The next three lines with n integers each gives the elements of the matrix ( | Ai,j | <= 10000).

Output

For each test case, print one line with an integer.

Sample Input

5 3 1 2 -10 3 5 3 -2 -10 2 -10 -10 -10 1 -10 -10 2 3 -1 -2 -3 -4 2 3

Sample Output

14 4

Source

FOJ有奖月赛-2011年11月

Submit  Back  Status  Discuss