H. Lemon Tang (Japanese Ver.)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Lemon Tang was an absolute success! H2H has since released a Japanese version, and they are now preparing to perform in Japan to promote it (as well as their upcoming single!).

H2H is running choreo drills with their backup dancers, forming a line of $$$n$$$ people in total. Not everyone coaches the same way, though: the H2H members can keep an eye on a big chunk of the formation, while some backup dancers can only focus on the people right next to them. Dancer $$$i$$$ has a coaching radius of $$$r_i$$$.

They can run at most $$$k$$$ training sessions. A training session consists of picking a single dancer to lead, who then works with themselves and everyone within their coaching radius. Formally, if dancer $$$i$$$ leads a session, every dancer $$$j$$$ such that $$$|i-j| \le r_i$$$ has their dance score $$$d_j$$$ increase by $$$+1$$$. The same dancer may lead any number of sessions.

The performance will only be as strong as its weakest performer, i.e. the person with the smallest $$$d_j$$$. Can you help maximize this value?

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 2 \cdot 10^5$$$): the number of dancers and the number of training sessions.

The second line contains $$$n$$$ space-separated integers $$$d_1, d_2, \ldots, d_n$$$ ($$$1 \le d_i \le 10^9$$$), where $$$d_i$$$ is the dance score of the $$$i$$$th dancer.

The third line contains $$$n$$$ space-separated integers $$$r_1, r_2, \ldots, r_n$$$ ($$$0 \le r_i \le n$$$), where $$$r_i$$$ is the coaching radius of the $$$i$$$th dancer.

Output

Output a single integer, denoting the maximum value of $$$\min_i d_i$$$ after assigning training sessions optimally.

Examples
Input
5 3
3 1 4 1 5
0 1 0 2 0
Output
3
Input
6 2
2 5 2 5 2 2
3 0 0 1 0 2
Output
3
Note

In the first sample, two sessions led by dancer $$$4$$$ achieve a minimum score of $$$3$$$: $$$$$$[3,1,4,1,5] \to [3,2,5,2,6] \to [3,3,6,3,7]$$$$$$

In the second sample, one session each led by dancers $$$1$$$ and $$$6$$$ achieves $$$3$$$. Reaching $$$4$$$ needs two sessions per endpoint, and no session covers both.

It may help to listen to the following song: https://open.spotify.com/track/7Duc0A2ye1eKwfCICOXYGT?si=f1e9ad0fd6e846cf