Binary String Game
题号:NC262397
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 512 M,其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

你有一个长度为 n 的二进制字符串 s,现在你可以进行无限次以下操作:

选取字符串中的恰好 m 个位置然后反转他们的值,即异或上 1

0 状态下的分数为 0,令第 i 个位置最后为 1 能带来的贡献分数为 a_i,求贡献分数最大为多少,并给出操作方案。

输入描述:

第一行两个正整数 n,m(1\leq m\leq n\leq 10^3)
第二行给定长度为 n 的 01 字符串 s
接下来一行给定 n 个整数 a_i(-10^9\leq a_i\leq 10^9)

输出描述:

第一行两个数 ans,p 分别表示答案和你给出操作方案的操作次数,你的操作方案需要满足 p\leq 5\times 10^4

接下来 p 行每行一个 01 字符串表示这次操作中每个位置是否异或上 1,需要保证 1 的个数恰好为 m
示例1

输入

复制
3 2
000
2 3 9

输出

复制
12 1
011