Panel Activation#13043
Sign in

Panel Activation

2 seconds
256 megabytes
Hard

You are given a binary array of length and an array of length .

You may perform the following operation at most once.

Choose an index . If s_i=0, then the operation is allowed only if

c_i \le k.

If s_i=1, the operation is always allowed.

After choosing :

  1. Set s_i=1.

  2. Let be the largest index such that

    l<i,\quad s_l=0,\quad c_l<c_i.

    If such an index exists, set s_l=1.

  3. Let be the smallest index such that

    r>i,\quad s_r=0,\quad c_r<c_i.

    If such an index exists, set s_r=1.

The indices and are determined using the array before the operation.

Find the maximum possible length of a contiguous segment consisting only of ones after performing the operation at most once.

Input

The first line contains two integers and (1 \le n \le 2 \cdot 10^5, 0 \le k \le 10^{9}).

The second line contains integers s_1,s_2,\ldots,s_n (s_i \in \{0,1\}).

The third line contains integers c_1,c_2,\ldots,c_n (0 \le c_i \le 10^9).

Output

Print one integer — the maximum possible length of a contiguous segment consisting only of ones after performing the operation at most once.

Examples

Example 1

Loading
Loading

Note

In the example, choose i=5.

Since s_5=0 and c_5=3\le k, this operation is allowed.

The corresponding indices on the left and on the right are and , since

c_3=1<c_5

and

c_7=2<c_5.

After the operation,

s=[1,0,1,1,1,1,1].

Thus, the answer is .

Scoring

  1. Subtask ( points): n \le 30.

  2. Subtask ( points): n \le 5000.

  3. Subtask ( points): No additional constraints.