Description

One day, Jiajia and Wind went out to plant trees with their m-2 children. They believe that trees should be in couples, just like human beings, so they decided to plant an even number of trees, say, 2n trees, in two rows, with n trees in each row. Planting some trees are more difficult than planting some others, so Jiajia carefully measured the difficulty value of each tree and wants to divide the trees into m sets, one for each of the m people to work with.

Each of the m people should plant all the trees in a rectangular with sides parallel to the axis. The difficulty value of a person is the sum of difficulty values of all trees he plants. Since Jiajia should always take the heaviest job (no, he can't leave the most difficult task to his honey, Wind, or their lovely children), Jiajia would like to make his own life easier by minimizing the maximal difficulty value over all the m tasks.

The figure of sample input is below. Different colors represent different jobs. There are only 3 people (Jiajia, Wind and Autumn) in this sample, but your program should be able to handle more complex situations, in which Jiajia and Wind have a loooooot of chilren :)

Input

The first line of input contains two integers n and m, the following two lines contain n integers each, representing the difficulty values of each tree, from left to right. You may assume that n<10001, m<=min{2*n,1000}. The sum of all difficulty values would not exceed 2

³⁰

.

Output

The output should contain a single integer, the minimized difficulty value of Jiajia's task.

3 3
1 2 6
2 1 6

6

Source

POJ Monthly--2006.02.26

,zgl & twb