Codeforces Round 626 (Div. 1, based on Moscow Open Olympiad in Informatics)


A. Unusual Competitions
time limit per test: 1 second
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
8
))((())(
Output
6
Input
3
(()
Output
-1
----------------------------------------------------------------------------------------------------
B. Present
time limit per test: 3 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
2
1 2
Output
3
Input
3
1 2 3
Output
2
----------------------------------------------------------------------------------------------------
C. Instant Noodles
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
2 4
1 1
1 1
1 2
2 1
2 2
3 4
1 1 1
1 1
1 2
2 2
2 3
4 7
36 31 96 29
1 2
1 3
1 4
2 2
2 4
3 1
4 3
Output
2
1
12
----------------------------------------------------------------------------------------------------
D. Reality Show
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
5 4
4 3 1 2 1
1 2 1 2 1
1 2 3 4 5 6 7 8 9
Output
6
Input
2 2
1 2
0 0
2 1 -100 -100
Output
2
Input
5 4
4 3 2 1 1
0 2 6 7 4
12 12 12 6 -3 -5 3 10 -4
Output
62
----------------------------------------------------------------------------------------------------
E. Median Mountain Range
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
5
1 2 1 2 1
Output
2
1 1 1 1 1 
Input
6
1 3 2 5 4 6
Output
1
1 2 3 4 5 6 
Input
6
1 1 2 2 1 1
Output
0
1 1 2 2 1 1 
----------------------------------------------------------------------------------------------------
F. Assigning Fares
time limit per test: 6 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3 1
1 2
2 3
1 3
Output
3
1 2 3
Input
4 3
1 2
1 3
1 4
2 3
2 4
3 4
Output
-1
Input
7 5
3 4
4 2
2 5
5 1
2 6
4 7
1 3
6 7
3 7
2 1
3 6
Output
-1
----------------------------------------------------------------------------------------------------
