数组

数组

题号：NC259244
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给出三个下标从 $1$ 开始、长度为 $n$ 的正整数数组 $A$ ， $K$ ， $C$ 。对于每个下标 $i\in[1,n]$ ，存在右边界 $r_i\in[i-1,n]$ ，其中 $r_i$ 满足两个要求。

要求 $1$ ： $\sum_{j=i}^{r_i}A_j\le K_i\times C_i$ 。

要求 $2$ ： $\sum_{j=i}^{r_i+1}A_j>K_i\times C_i$ 。

如果 $r_i=i-1$ ，默认要求 $1$ 满足。如果 $r_i=n$ ，默认要求 $2$ 满足。显然， $r_i$ 是唯一的。

每次操作可以选择一个下标 $j$ ，令 $C_j=C_j+1$ 。

定义数组的满意度为：得出长度为 $n$ 的数组 $B$ ，其中 $B_i=r_i-i+1$ 。设数组 $B$ 的最大值为 $Max$ ，最小值为 $Min$ ，满意度为 $Max-Min$ 。

给出一个整数 $m$ ，问：至多执行 $m$ 次操作的情况下，数组的最小满意度是多少？

输入描述:

第一行包含两个整数 $n\ m\ (1\le n,m\le2\times10^5)$ ，分别表示数组长度和操作次数限制。

第二行包含 $n$ 个整数 $A_i\ (1\le A_i\le10^9)$ 。

第三行包含 $n$ 个整数 $K_i\ (1\le K_i\le10^9)$ 。

第四行包含 $n$ 个整数 $C_i\ (1\le C_i\le10^9)$ 。

输出描述:

输出一行包含一个整数，表示最小满意度。

示例1

输入

复制

输出

复制

说明

在没有任何操作前，数组 ，。

备注: