Codeforces Round 684 (Div. 1)


A1. Binary Table (Easy Version)
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
2 2
10
11
3 3
011
101
110
4 4
1111
0110
0110
1111
5 5
01011
11001
00010
11011
10000
2 3
011
101
Output
1
1 1 2 1 2 2
2 
2 1 3 1 3 2
1 2 1 3 2 3
4
1 1 1 2 2 2 
1 3 1 4 2 3
3 2 4 1 4 2
3 3 4 3 4 4
4
1 2 2 1 2 2 
1 4 1 5 2 5 
4 1 4 2 5 1
4 4 4 5 3 4
2
1 3 2 2 2 3
1 2 2 1 2 2
----------------------------------------------------------------------------------------------------
A2. Binary Table (Hard Version)
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
2 2
10
11
3 3
011
101
110
4 4
1111
0110
0110
1111
5 5
01011
11001
00010
11011
10000
2 3
011
101
Output
1
1 1 2 1 2 2
2 
2 1 3 1 3 2
1 2 1 3 2 3
4
1 1 1 2 2 2 
1 3 1 4 2 3
3 2 4 1 4 2
3 3 4 3 4 4
4
1 2 2 1 2 2 
1 4 1 5 2 5 
4 1 4 2 5 1
4 4 4 5 3 4
2
1 3 2 2 2 3
1 2 2 1 2 2
----------------------------------------------------------------------------------------------------
B. Graph Subset Problem
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
5 9 4
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
10 15 3
1 2
2 3
3 4
4 5
5 1
1 7
2 8
3 9
4 10
5 6
7 10
10 8
8 6
6 9
9 7
4 5 4
1 2
2 3
3 4
4 1
1 3
Output
2
4 1 2 3 
1 10
1 2 3 4 5 6 7 8 9 10 
-1
----------------------------------------------------------------------------------------------------
C. Greedy Shopping
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
10 6
10 10 10 6 6 5 5 5 3 1
2 3 50
2 4 10
1 3 10
2 2 36
1 4 7
2 2 17
Output
8
3
6
2
----------------------------------------------------------------------------------------------------
D. INOI Final Contests
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 1 1000000007
Output
0
Input
2 2 1000000009
Output
4
Input
3 2 998244353
Output
8
Input
20 10 1000000009
Output
352081045
----------------------------------------------------------------------------------------------------
E. Cheat and Win
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
1
7 0 0 7
Output
1
Input
3
1 2 3 4
3 4 1 2
2 1 3 4
Output
3
Input
2
0 1 0 8
1 0 8 0
Output
0
----------------------------------------------------------------------------------------------------
