406334: GYM102365 D Astrodirections

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.

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 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.

16 8
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5

20

16 2
2 0
33 33

30

10 5
50 60 70 80 90
5 4 3 2 1

185