该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

某中学计算机社团成员麦麦负责维护学校自习室的灯光系统。这间自习室有 n 个座位，编号从 1 到 n 排成一行，每个座位上的灯光亮度各不相同。为了提升同学们的学习效率，麦麦打算通过系统对灯光进行调亮操作。

题目描述

系统允许执行至多 k 次“调亮操作”。每次操作可以选择一个连续的座位区间 $[l, r]$，并让该区间内所有座位的灯光亮度同时增加 1。但由于电路老化，每个座位最多只能承受有限次的调亮操作，超过限制后灯泡将会烧坏。

现给定：

• 每个座位当前的灯光亮度 $a_i$；
• 每个座位可承受的最大调亮次数 $c_i$。

请你帮助麦麦设计操作方案，使得经过不超过 k 次调亮操作后，所有座位中最暗的那个座位的亮度达到最大值。输出该最大可能的最小亮度。

输入格式

第一行：两个整数 $n, k$，表示座位数量和可用的调亮操作次数。
第二行：$n$ 个整数 $a_1, a_2, \dots, a_n$，表示各座位当前亮度。
第三行：$n$ 个整数 $c_1, c_2, \dots, c_n$，表示各座位可承受的最大调亮次数。

输出格式

一个整数，表示通过最优操作方案后，所有座位的最小亮度的最大可能值。

样例

5 5
10 8 12 6 9
3 2 4 4 2

10

3 3
5 5 5
1 1 1

6

样例解释

样例 1：
一种可行方案是：

1. 将第 2 个座位单独调亮 1 次（剩余操作 4 次）。
2. 将第 4 个座位单独调亮 2 次（剩余操作 2 次）。
3. 对区间 $[2,4]$ 调亮 1 次（剩余操作 1 次）。
4. 对区间 $[4,5]$ 调亮 1 次（剩余操作 0 次）。

此时座位亮度依次为 10, 10, 13, 10, 10，最暗座位亮度为 10。

数据范围

本题共 10 个测试点。
$1 ≤ n ≤ 10^5，1 ≤ k, a_i, c_i ≤ 10^9$。
测试点细分：

• 测试点 1–2：$n, k, a_i, c_i ≤ 10$
• 测试点 3–5：$n, k, a_i, c_i ≤ 1000$
• 测试点 6：$n = 1$
• 测试点 7–10：$n, k ≤ 10^5，a_i, c_i ≤ 10^9$

附件