Codeforces Round 765 (Div. 2)


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

Examples
Input
7
3 5
18 9 21
3 5
18 18 18
1 1
1
5 30
1 2 3 4 5
6 10
99 35 85 46 78 55
2 1
0 1
8 8
5 16 42 15 83 65 78 42
Output
17
18
1
1
39
0
2
----------------------------------------------------------------------------------------------------
B. Elementary Particles
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
7
3 1 5 2 1 3 4
6
1 1 1 1 1 1
6
1 4 2 8 5 7
2
15 15
Output
4
5
-1
1
----------------------------------------------------------------------------------------------------
C. Road Optimization
time limit per test: 3 seconds
memory limit per test: 128 megabytes
input: standard input
output: standard output

Examples
Input
4 10 0
0 3 4 8
5 8 3 6
Output
47
Input
4 10 2
0 3 4 8
5 8 3 6
Output
38
----------------------------------------------------------------------------------------------------
D. Binary Spiders
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6 8
2 8 4 16 10 14
Output
3
1 5 4
Input
6 1024
1 2 3 1 4 0
Output
-1
----------------------------------------------------------------------------------------------------
E1. Cats on the Upgrade (easy version)
time limit per test: 6 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
9 4
)(()())()
2 3 6
2 2 7
2 8 9
2 2 9
Output
3
4
1
6
----------------------------------------------------------------------------------------------------
E2. Cats on the Upgrade (hard version)
time limit per test: 6 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
9 8
)(()())()
2 3 6
2 2 7
1 3 4
2 2 7
2 2 9
1 5 6
1 2 7
2 8 9
Output
3
4
2
4
1
----------------------------------------------------------------------------------------------------
