科技节即将开幕,工作人员正在调试展厅里的灯光。
展厅中的展位排成一行,有些展位的灯光较亮,需要用遮光片进行调整。共有 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、2 个展位后,剩余最大亮度为 8。由于不能跨过第 2 个展位后的隔板,一张遮光片不能同时遮住亮度 9 和 8 的展位,不能得到更小的结果。
没有隔板,可以覆盖第 1 至 3 个展位,剩余最大亮度为 7。
遮住唯一的展位即可。