Codeforces Round 591 (Div. 1, based on Technocup 2020 Elimination Round 1)


A. Save the Nature
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
1
100
50 1
49 1
100
8
100 200 100 200 100 200 100 100
10 2
15 3
107
3
1000000000 1000000000 1000000000
50 1
50 1
3000000000
5
200 100 100 100 100
69 5
31 2
90
Output
-1
6
3
4
----------------------------------------------------------------------------------------------------
B. Sequence Sorting
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
7
3 1 6 6 3 1 1
8
1 1 4 4 4 7 8 8
7
4 2 5 2 6 2 7
Output
2
0
1
----------------------------------------------------------------------------------------------------
C. Paint the Tree
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2
4 1
1 2 5
3 1 2
3 4 3
7 2
1 2 5
1 3 4
1 4 2
2 5 1
2 6 2
4 7 3
Output
8
14
----------------------------------------------------------------------------------------------------
D. Stack Exterminable Arrays
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
5
2 1 1 2 2
6
1 2 1 1 3 2
9
3 1 2 2 1 6 6 3 3
Output
4
1
8
----------------------------------------------------------------------------------------------------
E. Wooden Raft
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
1
9
Output
4
Input
9
9 10 9 18 9 9 9 28 9
Output
90
----------------------------------------------------------------------------------------------------
F. Football
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7 11 3
4 7 8 10 10 9 3
6 2
6 1
7 6
4 3
4 6
3 1
5 3
7 5
7 3
4 2
1 4
Output
3
2
1
1
3
1
2
1
2
3
2
----------------------------------------------------------------------------------------------------
