C. Legendary Drop
time limit per test
4 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Teadose(IanISam) has been getting "Legendary Drops" $$$ $$$ in his recent codeforces contests. After learning about persistent data structures, Teadose can now time travel and warn his past self to not take at most one contest(Teadose refuses to skip more than one round) to minimize the Legendary Drop*.

Teadose will participate in $$$n$$$ contests, the $$$i^{th}$$$ of which Teadose has a performance of $$$p_i$$$ and is a division $$$d_i$$$ contest, where $$$d_i$$$ denotes the division of the contest modulo 2. Teadose will take only Division $$$1$$$ and $$$2$$$ rounds and his rating, $$$r$$$ after a contest $$$i$$$ will be: $$$$$$ \begin{cases} r & d_i = 0 , r \ge 2100\\ r & d_i = 1, r \lt 1900 \\ r + f(\frac{(p-r)}{4}) & \text{else} \end{cases} $$$$$$ Here $$$f(x)$$$ rounds x to an integer closer to zero. For example $$$f(1.5)=1$$$, $$$f(-1.5)=-1$$$, $$$f(-1)=-1$$$. Find the minimum Legendary drop Teadose will get if he warns himself on at most one contest. Note: Teadose does not have to warn his past self if taking all contests will already minimize his Legendary Drop.

*The minimum Legendary Drop is minimizing Teadose's initial rating - Teadose's final rating

Input

The first line contains two integers $$$n$$$ $$$(1\leq n\leq 10^5)$$$ and $$$k$$$ $$$(0\leq k\leq 4000)$$$ the number of contests and Teadose's initial rating

The second line contains $$$n$$$ integers, $$$p_1, p_2, p_3 ... p_n$$$ $$$(0\leq p_i\leq 4000)$$$ Teadose's performance on the $$$i^{th}$$$ contest

The third line contains $$$n$$$ integer $$$d_1, d_2, d_3 ... d_n$$$ $$$ (d_i ={0, 1})$$$ the division of the $$$i^{th}$$$ contest where $$$0$$$ indicates that the $$$i^{th}$$$ contest is division $$$2$$$ and $$$1$$$ indicating a division $$$1$$$ contest

Output

Print one integer, Teadose's minimum Legendary Drop if he can avoid at most one contest

Examples
Input
5 1800
2444 1689 1861 1577 1736
0 1 0 0 0
Output
-48
Input
2 2100
1296 0
1 1
Output
201
Note

On the first test, it is optimal to skip the $$$4^{th}$$$ contest $$$1800 \xrightarrow[\text{rated}]{(div2, p2444)} 1961 \xrightarrow[\text{rated}]{(div1, p1689)} 1893 \xrightarrow[\text{rated}]{(div2, p1861)} 1885 \xrightarrow[\text{skipped}]{(div2, p1588)} 1885 \xrightarrow[\text{rated}]{(div2, p1736)} 1848$$$

Thus the minimum legendary drop possible is $$$1800 - 1848 = -48$$$

On the second test, one optimal solution is taking every contest.

$$$2100 \xrightarrow[\text{rated}]{(div1, p1296)} 1899 \xrightarrow[\text{unrated}]{(div1, p0)} 1899$$$

Thus the minimum legendary drop possible is $$$2100 - 1899 = 201$$$