#700. 【候选队互测2022】可爱多的字符串

样例一

input

10 10
1110110001
3 1 4 1 5 9 2 6 5 3
6 9
1 5
4 6
5 10
6 8
3 9
7 9
9 10
6 6
6 9



output

22
28
15
42
17
48
29
8
9
22



限制与约定

1 $10^4$ 5
2 $10^5$ $w_i=1,r=n$ 10
3 $10^5$ $r=n$ 20 2
4 $10^5$ $w_i=1$，字符串的每个字符在 $\{0,1\}$ 中随机 10
5 $10^5$ 字符串的每个字符在 $\{0,1\}$ 中随机 10 4
6 $10^5$ $w_i=1$ 5 2,4
7 $10^5$ 20 1,3,5,6
8 $2\times 10^5$ 20 7