Codeforces Round 745 (Div. 1)


A. Portal
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
1
5 4
1000
0000
0110
0000
0001
Output
12
Input
1
9 9
001010001
101110100
000010011
100000001
101010101
110001111
000001111
111100000
000110000
Output
5
----------------------------------------------------------------------------------------------------
B. Mathematics Curriculum
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4 3 2 10007
Output
4
Input
6 4 1 769626776
Output
472
Input
66 11 9 786747482
Output
206331312
Input
99 30 18 650457567
Output
77365367
----------------------------------------------------------------------------------------------------
C. Train Maintenance
time limit per test: 1 second
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3 4
10 15
12 10
1 1
1 3
1 1
2 1
2 3
Output
0
1
0
0
Input
5 4
1 1
10000000 100000000
998244353 1
2 1
1 2
1 5
2 5
1 5
1 1
Output
0
0
0
1
----------------------------------------------------------------------------------------------------
D. Subsequence
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6 4
15 2 18 12 13 4
Output
100
Input
11 5
9 3 7 1 8 12 10 20 15 18 5
Output
176
Input
1 1
114514
Output
0
Input
2 1
666 888
Output
0
----------------------------------------------------------------------------------------------------
E. Railway Construction
time limit per test: 2.5 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
5 5 1
1 1 1 1 1
1 2 1
2 3 1
2 4 1
3 5 1
4 5 1
1 2
Output
3
9
Input
8 11 0
14 4 16 15 1 3 1 14
4 2 1
1 2 3
7 5 4
2 3 1
8 6 2
8 5 5
5 4 5
7 6 7
3 5 5
1 6 6
8 1 4
Output
46
Input
10 16 8
29 1 75 73 51 69 24 17 1 97
1 2 18
2 3 254
2 4 546
2 5 789
5 6 998
6 7 233
7 8 433
1 9 248
5 10 488
2 6 1787
10 8 1176
3 8 2199
4 8 1907
2 10 1277
4 10 731
9 10 1047
1 11
1 9
8 8
1 3
2 19
9 5
9 4
7 6
Output
34
45
54
54
57
76
96
112
112
----------------------------------------------------------------------------------------------------
F. Problems for Codeforces
time limit per test: 8 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 2
Output
4
Input
5 9
Output
8105
Input
21038 3942834
Output
338529212
----------------------------------------------------------------------------------------------------
