Cafeteria Queue Clearance

In the cafeteria there are n regions. Initially, region i has a_i waiting students and b_i empty seats. It is guaranteed that \(\sum_{i=1}^{n}a_i \le \sum_{i=1}^{n}b_i\).

At the moment the cafeteria opens, exactly k of the waiting students (due to being in a hurry) decide to leave immediately with their food packed. However, the exact regions from which these k students leave is unknown. Immediately after opening, time evolves in discrete steps. At each time step the following two events occur in order:

1. Seating: In every region i, let the current waiting count be \(x_i\) and the empty seat count be \(y_i\). Then:
   • If \(x_i \le y_i\), all \(x_i\) students get seated, leaving \(y_i - x_i\) empty seats and no student waiting in region i.
   • If \(x_i > y_i\), exactly \(y_i\) students get seated (filling all the seats) and \(x_i - y_i\) remain waiting.
2. Movement: Every student that is still waiting in region i moves simultaneously to region \((i \bmod n) + 1\) (i.e. the next region in cyclic order).

For any possible way of distributing the k departing students among the regions (subject to each region losing at most its own \(a_i\) students), we wish to know the minimum number of time steps (after opening) that will guarantee that every region has no waiting student.

Important: The adversary (who determines the distribution of the k students who leave) will choose the distribution that maximizes the overall clearance time. In other words, if we denote the number of waiting students in region i after the departing students leave by \(c_i\), then the clearance condition for a region is based on the dynamics:

After t time steps, a student originally in region i will have passed through regions \(i, i+1, \ldots, i+t-1\) (cyclically) and will get seated if the total number of seats available in these regions is at least the number of waiting students that stayed in region i (i.e. if \(\sum_{j=0}^{t-1}b_{(i+j) \bmod n} \ge c_i\)).

The adversary can choose the removals \(d_i\) (with \(0 \le d_i \le a_i\) and \(\sum_{i=1}^{n}d_i = k\)) arbitrarily. To maximize the clearance time, the adversary will try to avoid reducing the waiting count in the region that is the bottleneck for seating. Specifically, for each region i one can define a clearance function:

[ f(i, w) = \min\Big{ t ;:; \sum_{j=0}^{t-1} b_{((i+j) \bmod n)} \ge w \Big} ]

If the adversary can avoid taking any students from a region, then its effective waiting remains \(a_i\). This is possible for region \(i\) if \(\sum_{j\neq i}a_j \ge k\). Otherwise, the adversary is forced to remove at least \(k - \big(\sum_{j\neq i}a_j\big)\) students from region i, so its effective waiting becomes \(a_i' = a_i - \Big(k - (\sum_{j\neq i}a_j)\Big) = 2a_i - k - \sum_{j=1}^{n}a_j\).

Thus, for each region i, the worst‐case clearance time is given by:

[ T_i = \begin{cases} f(i, a_i), & \text{if } \sum_{j\neq i}a_j \ge k,\[1mm] f(i, 2a_i - k - \sum_{j=1}^{n}a_j), & \text{otherwise.} \end{cases} ]

The answer to the problem is \(\max_{1 \le i \le n} T_i\).

inputFormat

The first line contains two integers n and k — the number of regions in the cafeteria and the number of students who leave immediately, respectively.

The second line contains n integers: a₁, a₂, ..., a_n where a_i is the number of waiting students in region i initially.

The third line contains n integers: b₁, b₂, ..., b_n where b_i is the number of empty seats in region i.

It is guaranteed that \(\sum_{i=1}^{n}a_i \le \sum_{i=1}^{n}b_i\) and \(0 \le k \le \sum_{i=1}^{n}a_i\).

outputFormat

Output a single integer — the minimum number of time steps after which every region will have no waiting student, no matter how the k departing students are distributed.

sample

1 0
5
5

1