Codeforces Round 333 (Div. 1)


A. The Two Routes
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4 2
1 3
3 4
Output
2
Input
4 6
1 2
1 3
1 4
2 3
2 4
3 4
Output
-1
Input
5 5
4 2
3 5
4 5
5 1
1 2
Output
3
----------------------------------------------------------------------------------------------------
B. Lipshitz Sequence
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
10 4
1 5 2 9 1 3 4 2 1 7
2 4
3 8
7 10
1 9
Output
17
82
23
210
Input
7 6
5 7 7 4 6 6 2
1 2
2 3
2 6
1 7
4 7
3 5
Output
2
0
22
59
16
8
----------------------------------------------------------------------------------------------------
C. Kleofáš and the n-thlon
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4 10
2
1
2
1
Output
1.0000000000000000
Input
5 5
1
2
3
4
5
Output
2.7500000000000000
Input
3 6
2
4
2
Output
1.6799999999999999
----------------------------------------------------------------------------------------------------
D. Acyclic Organic Compounds
time limit per test: 3 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
10
1 2 7 20 20 30 40 50 50 50
cacabbcddd
1 2
6 8
7 2
6 2
5 4
5 9
3 10
2 5
2 3
Output
51
3
Input
6
0 2 4 1 1 1
raaaba
1 2
2 3
2 4
2 5
3 6
Output
6
2
----------------------------------------------------------------------------------------------------
E. A Museum Robbery
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 10
30 4
60 6
5 1
9
3
1 42 5
1 20 3
3
2 2
2 4
3
1 40 6
3
Output
556674384
168191145
947033915
181541912
Input
3 1000
100 42
100 47
400 15
4
2 2
2 1
2 3
3
Output
0
----------------------------------------------------------------------------------------------------
