Codeforces Round 219 (Div. 1)


A. Counting Kangaroos is Fun
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
8
2
5
7
6
9
8
4
2
Output
5
Input
8
9
1
6
2
6
5
8
3
Output
5
----------------------------------------------------------------------------------------------------
B. Counting Rectangles is Fun
time limit per test: 4 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5 5 5
00101
00000
00001
01000
00001
1 2 2 4
4 5 4 5
1 2 5 2
2 2 4 5
4 2 5 3
Output
10
1
7
34
5
Input
4 7 5
0000100
0000010
0011000
0000000
1 7 2 7
3 1 3 1
2 3 4 5
1 2 2 7
2 2 4 7
Output
3
1
16
27
52
----------------------------------------------------------------------------------------------------
C. Watching Fireworks is Fun
time limit per test: 4 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
50 3 1
49 1 1
26 1 4
6 1 10
Output
-31
Input
10 2 1
1 1000 4
9 1000 4
Output
1992
----------------------------------------------------------------------------------------------------
D. Choosing Subtree is Fun
time limit per test: 5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
10 6
4 10
10 6
2 9
9 6
8 5
7 1
4 7
7 3
1 8
Output
3
Input
16 7
13 11
12 11
2 14
8 6
9 15
16 11
5 14
6 15
4 3
11 15
15 14
10 1
3 14
14 7
1 7
Output
6
----------------------------------------------------------------------------------------------------
E. Drawing Circles is Fun
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
10
-46 46 0 36
0 20 -24 48
-50 50 -49 49
-20 50 8 40
-15 30 14 28
4 10 -4 5
6 15 8 10
-20 50 -3 15
4 34 -16 34
16 34 2 17
Output
2
Input
10
30 30 -26 26
0 15 -36 36
-28 28 -34 34
10 10 0 4
-8 20 40 50
9 45 12 30
6 15 7 35
36 45 -8 20
-16 34 -4 34
4 34 8 17
Output
4
Input
10
0 20 38 38
-30 30 -13 13
-11 11 16 16
30 30 0 37
6 30 -4 10
6 15 12 15
-4 5 -10 25
-16 20 4 10
8 17 -2 17
16 34 2 17
Output
10
----------------------------------------------------------------------------------------------------
