Educational Codeforces Round 3


A. USB Flash Drives
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
5
2
1
3
Output
2
Input
3
6
2
3
2
Output
3
Input
2
5
5
10
Output
1
----------------------------------------------------------------------------------------------------
B. The Best Gift
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4 3
2 1 3 1
Output
5
Input
7 4
4 2 3 1 2 4 3
Output
18
----------------------------------------------------------------------------------------------------
C. Load Balancing
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2
1 6
Output
2
Input
7
10 11 10 11 10 11 11
Output
0
Input
5
1 2 3 4 5
Output
3
----------------------------------------------------------------------------------------------------
D. Gadgets for dollars and pounds
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5 4 2 2
1 2 3 2 1
3 2 1 2 3
1 1
2 1
1 2
2 2
Output
3
1 1
2 3
Input
4 3 2 200
69 70 71 72
104 105 106 107
1 1
2 2
1 2
Output
-1
Input
4 3 1 1000000000
900000 910000 940000 990000
990000 999000 999900 999990
1 87654
2 76543
1 65432
Output
-1
----------------------------------------------------------------------------------------------------
E. Minimum spanning tree for each edge
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5 7
1 2 3
1 3 1
1 4 5
2 3 2
2 5 3
3 4 2
4 5 4
Output
9
8
11
8
8
8
9
----------------------------------------------------------------------------------------------------
F. Frogs and mosquitoes
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
4 6
10 2
15 0
6 1
0 1
110 10
1 1
6 0
15 10
14 100
12 2
Output
3 114
1 10
1 1
1 2
Input
1 2
10 2
20 2
12 1
Output
1 3
----------------------------------------------------------------------------------------------------
