Sequential Manufacturing

A manufacturing process consists of $N$ different machines. Raw material passes through the machines in order until it becomes a finished good. Machine $i$ takes $T_i$ seconds to process a good once it is input.

A good moves through the system automatically after it enters the first machine. To give the system some slack, each machine $i$ has an input area that holds up to $K_i$ goods waiting to be processed by that machine. When machine $i$ finishes a good, the good moves on to machine $i + 1$ right away if that machine is free. Otherwise it waits in the input area of machine $i + 1$ until the machine becomes free. If machine $i$ finishes a good while machine $i + 1$ is busy and its input area is full, the system shuts down. If machines $i$ and $i + 1$ finish goods at the same moment, the good from machine $i$ does not need to go through the input area of machine $i + 1$ first.

You just received a huge order. You have an infinite supply of raw material, and you can choose the times at which goods enter machine 1. How quickly can you finish all of these goods without the system shutting down?

The first line contains two integers $N$ ($1 \le N \le 1\,000$), the number of machines, and $P$ ($1 \le P \le 10^9$), the number of goods to produce.

The next line contains the processing times $T_1, \dots, T_N$ ($1 \le T_i \le 10^9$), all integers.

The next line contains the sizes of the input areas $K_2, \dots, K_N$ ($1 \le K_i \le 10^9$), all integers. The first machine has no input area.

Output the number of seconds needed to produce all $P$ goods. Manufacturing is complete when the last good is processed by the last machine.