406334: GYM102365 D Astrodirections

Memory Limit:1024 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Astrodirectionstime limit per test1 secondmemory limit per test1024 megabytesinputstandard inputoutputstandard output

It is a very rare event that all $$$N$$$ colonized planets in the galaxy, numbered $$$1,2,\ldots,N$$$, align in order on a straight line. To celebrate the occasion, a grand Astrofestival is held on one of the planets, where unhealthy amounts of Astrohol will be consumed.

Astrodavid doesn't know what Astrohol is, but he's very excited about the Astrogeometry meetup that will take place at the Astrofestival. Unfortunately, he doesn't know on which planet it's held. He may Astrojump between planets on his Astroship, but he has to buy fuel first. Luckily, he reached the fuel station on his home planet just before it closes for the Astrofestival. How much fuel must Astrodavid buy to guarantee that he'll make it to the Astrofestival?

Astrodavid lives on planet $$$1$$$. His Astroship has jump power $$$J$$$. To take off from planet $$$p$$$, he chooses an Astrojump displacement $$$i$$$ such $$$1\le |i|\le J$$$, $$$1\le p+i\le N$$$, and his fuel supply is at least $$$f_i$$$ units. He will then land on planet $$$p+i$$$, his fuel supply having decreased by $$$f_i$$$ units. Upon asking for directions there, he'll know if the Astrofestival is held at that planet, a different planet with a higher number, or one with a lower number. As long as he has enough fuel, he may choose to Astrojump again.

Input

The first line contains two space-separated integers $$$N$$$ ($$$2\le N\le 4\,000$$$) and $$$J$$$ ($$$1\le J\le \frac N2$$$), the number of colonized planets and the jump power, respectively.

The second line contains $$$J$$$ integers, the $$$i$$$'th of which is $$$f_i$$$, the fuel cost of jumping upward by $$$i$$$ planets.

The third line contains $$$J$$$ integers, the $$$i$$$'th of which is $$$f_{-i}$$$, the fuel cost of jumping downward by $$$i$$$ planets.

For all $$$i$$$, $$$0 \le f_i \le 10\,000$$$.

Output

Output the minimum number of units of fuel that Astrodavid must buy to guarantee that he'll reach the festival, no matter where it's actually held.

ExamplesInput
16 8
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5
Output
20
Input
16 2
2 0
33 33
Output
30
Input
10 5
50 60 70 80 90
5 4 3 2 1
Output
185

加入题单

上一题 下一题 算法标签: