PEG Judge - WC15 #4 - Coded Paper

Woburn Challenge 2015-16 Round 4 - Senior Division

Problem 3: Coded Paper

Bond has gotten his hands on a mysterious slip of paper. It's divided into a grid of square cells, with 2 rows and N (1 ≤ N ≤ 10⁵) columns. The j-th cell in the i-th row has the integer C_{i, j} (−100 ≤ C_{i, j} ≤ 100) printed in it.

Bond also has access to a curious machine which can print rectangular pieces of cardboard on demand. He can use it to print as many rectangles as he'd like, each of them having any integral dimensions of his choice. Each rectangle produced by this machine will have a single integer R (−100 ≤ R ≤ 100) printed on it, regardless of its size. Bond may choose to place these cardboard rectangles on top of the slip of paper such that they cover some of its cells, as long as they're aligned with the grid, they fit within the grid, and none of them overlap with one another.

He has reason to believe that the purpose of this slip of paper is actually to encode a single, secret integer, which is the maximum possible sum of visible integers after zero or more cardboard rectangles have been placed on it. This sum includes the integers written on the rectangles used, of course, and doesn't include any integers in cells which are underneath a rectangle. Can you help him crack the code by determining the maximum possible sum that can be achieved?

Subtasks

In test cases worth 2/25 of the points, N ≤ 2.
In test cases worth another 5/25 of the points, N ≤ 6.

Input Format

The first line of input consists of two space-separated integers N and R.
The second line consists of N integers, C_{1, 1..N}.
The third line consists of N integers, C_{2, 1..N}.

Output Format

Output a single integer, the maximum sum of visible integers that Bond can achieve by placing cardboard rectangles optimally.

Sample Input 1

4 -5
20 -10 -1 5
-2 3 1 -6

Sample Output 1

Explanation

Bond should place a 1×2 rectangle in the middle of the first row (covering −10 and −1), and a 1×1 rectangle in the bottom-right corner (covering −6). The visible numbers will then be 20, −5, 5, −2, 3, 1, and −5, which sum to 17.