Codeforces Round 433 (Div. 1, based on Olympiad of Metropolises)


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

Examples
Input
5 2
4 2 1 10 2
Output
20
3 6 7 4 5 
----------------------------------------------------------------------------------------------------
B. Jury Meeting
time limit per test: 1 second
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
2 6 5
1 1 0 5000
3 2 0 5500
2 2 0 6000
15 0 2 9000
9 0 1 7000
8 0 2 6500
Output
24500
Input
2 4 5
1 2 0 5000
2 1 0 4500
2 1 0 3000
8 0 1 6000
Output
-1
----------------------------------------------------------------------------------------------------
C. Boredom
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
2 3
1 2
1 1 1 1
1 1 1 2
1 1 2 2
Output
1
1
1
Input
4 2
1 3 2 4
4 1 4 4
1 1 2 3
Output
3
5
----------------------------------------------------------------------------------------------------
D. Michael and Charging Stations
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
1000 2000 1000
Output
3700
Input
6
2000 2000 2000 2000 2000 1000
Output
10000
----------------------------------------------------------------------------------------------------
E. Lada Malina
time limit per test: 5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2 4 1
1 1
-1 1
2 3 1
2 -2 1
-2 1 1
-2 -2 1
0 0 2
Output
3
Input
3 4 3
2 0
-1 1
-1 -2
-3 0 6
1 -2 1
-3 -7 3
3 2 2
-1 -4 1
0 4 2
6 0 1
Output
4
9
0
----------------------------------------------------------------------------------------------------
