VK Cup 2012 Round 1


A. Dress'em in Vests!
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5 3 0 0
1 2 3 3 4
1 3 5
Output
2
1 1
3 2
Input
3 3 2 2
1 5 9
3 5 7
Output
3
1 1
2 2
3 3
----------------------------------------------------------------------------------------------------
B. Discounts
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 2
2 1
3 2
3 1
Output
5.5
2 1 2
1 3
Input
4 3
4 1
1 2
2 2
3 2
Output
8.0
1 1
2 4 2
1 3
----------------------------------------------------------------------------------------------------
C. Abracadabra
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 6 1 4
Output
2
Input
1 1 4 4
Output
0
----------------------------------------------------------------------------------------------------
D. Distance in Tree
time limit per test: 3 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
5 2
1 2
2 3
3 4
2 5
Output
4
Input
5 3
1 2
2 3
3 4
4 5
Output
2
----------------------------------------------------------------------------------------------------
E. Polycarpus the Safecracker
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
11
239
401
9001
Output
4
28
61
2834
----------------------------------------------------------------------------------------------------
