6597 - 分区遮光

题目描述

科技节即将开幕,工作人员正在调试展厅里的灯光。

展厅中的展位排成一行,有些展位的灯光较亮,需要用遮光片进行调整。共有 n 个展位,从左到右编号为 1 至 n。

第 i 个展位的原始亮度为 a_i。相邻展位之间可能有隔板,把整排展位分成若干区。

最多可以使用 m 张遮光片。每张遮光片可以覆盖同一区内至多 k 个连续展位,不允许跨越隔板。

被 至少一张 遮光片覆盖的展位亮度变为 0,其余展位亮度不变。允许遮光片重叠,也可以不使用或少用遮光片。

请使操作后所有展位中的最大亮度尽可能小,并输出这个 最小值。如果所有展位的亮度都为 0,最大亮度就是 0。

输入

第一行输入三个整数 n,m,k。

第二行输入 n 个整数 a_1,a_2,\ldots,a_n。

当 n>1 时,第三行输入 n-1 个整数 w_1,w_2,\ldots,w_{n-1}:

w_i=1 表示第 i 与第 i+1 个展位之间有隔板,

w_i=0 表示没有。

当 n=1 时,不输入第三行。

输出

输出一个整数,表示能达到的最小最大亮度。

样例

输入

5 1 3
9 1 8 1 7
0 1 0 0

输出

8

输入

5 1 3
9 1 8 1 7
0 0 0 0

输出

7

输入

1 1 1
10

输出

0
说明

样例 1 解释

用一张遮光片覆盖第 1、2 个展位后,剩余最大亮度为 8。由于不能跨过第 2 个展位后的隔板,一张遮光片不能同时遮住亮度 9 和 8 的展位,不能得到更小的结果。

样例 2 解释

没有隔板,可以覆盖第 1 至 3 个展位,剩余最大亮度为 7。

样例 3 解释

遮住唯一的展位即可。

数据范围

  • 对于 30\% 的数据,1\le n\le1000,0\le a_i\le1000。
  • 对于 100\% 的数据,1\le n\le2\times10^5,0\le m\le n,1\le k\le n,0\le a_i\le10^9,w_i\in {0,1}。
  • 遮光片的长度为"至多 k",可以在隔板前提前结束。
标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 1
通过人数 1
金币数量 0 枚
难度 入门


上一题 下一题