#P18928. [2026多校联测]环灯校准

[2026多校联测]环灯校准

环灯校准

题目描述

观测结束后,维护员要关掉圆形平台上的全部指示灯。平台上有一台校准器,每次都要同时翻转相邻的若干盏灯,无法单独控制其中一盏。

共有 nn 盏灯,沿顺时针方向编号为 1,2,…,n1,2,\ldots,n。第 nn 盏的下一盏是第 11 盏。第 ii 盏灯的初始状态为 sis_i,其中 00 表示熄灭,11 表示点亮。

校准器的作用范围固定为 kk 盏灯。一次操作选择起点 ii,从第 ii 盏开始,沿顺时针方向将连续 kk 盏灯的状态全部翻转,即 00 变为 11、11 变为 00,费用为 wiw_i。当 k=nk=n 时,这次操作会翻转全部灯。可以多次选择同一个起点,每次分别付费。

请你求出关掉全部灯的最小总费用。也可以不操作;如果无论怎样操作都无法关掉全部灯,输出 −1-1。

输入格式

第一行两个整数 n,kn,k。

第二行 nn 个整数 s1,s2,…,sns_1,s_2,\ldots,s_n。

第三行 nn 个整数 w1,w2,…,wnw_1,w_2,\ldots,w_n。

输出格式

输出一个整数,表示最小总费用;无解时输出 −1-1。

样例 1 输入

4 2
1 1 0 0
5 2 4 3

样例 1 输出

5

样例 1 解释

只在起点 11 操作一次即可,费用为 55。也可以在其余三个起点各操作一次,但费用为 99,因此最小费用是 55。

样例 2 输入

3 2
1 0 0
1 2 3

样例 2 输出

-1

样例 2 解释

每次操作恰好翻转两盏灯,状态为 11 的灯的数量的奇偶性不变。初始只有一盏灯为 11,所以无解。

样例 3

见下发文件中的 phase/3.in 和 phase/3.ans。这是一组较大的样例,题面中不展开。

数据范围与子任务

对于所有测试数据,保证:1≤k≤n≤3000001\le k\le n\le300000,si∈{0,1}s_i\in\{0,1\},1≤wi≤1091\le w_i\le10^9。

本题共有四个子任务,各组独立计分。通过某组全部测试点,才能得到该组分数。

子任务 分值 额外约束
1 20 n≤18n\le18
2 k=1k=1 或 k=nk=n
3 gcd⁡(n,k)=1\gcd(n,k)=1
4 40 无额外约束