Tinkoff Challenge - Elimination Round


A. Oleg and shares
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 3
12 9 15
Output
3
Input
2 2
10 9
Output
-1
Input
4 1
1 1000000000 1000000000 1000000000
Output
2999999997
----------------------------------------------------------------------------------------------------
B. Igor and his way to work
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5 5
..S..
****.
T....
****.
.....
Output
YES
Input
5 5
S....
****.
.....
.****
..T..
Output
NO
----------------------------------------------------------------------------------------------------
C. Mice problem
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
7 7 9 8
3 5 7 5
7 5 2 4
3 3 7 8
6 6 3 2
Output
0.57142857142857139685
Input
4
7 7 9 8
0 3 -5 4
5 0 5 4
9 9 -1 -6
10 5 -7 -10
Output
-1
----------------------------------------------------------------------------------------------------
D. Presents in Bankopolis
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7 4
4
1 6 2
6 2 2
2 4 2
2 7 1
Output
6
Input
4 3
4
2 1 2
1 3 2
3 4 2
4 1 1
Output
3
----------------------------------------------------------------------------------------------------
E. Problem of offices
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
2 3 4 5
1 1 1 1
Output
YES
Input
10
3 8 9 10
1 2 2 2 2 2 1 1 1
Output
NO
Input
13
13 12 9 7
1 1 1 1 5 5 2 2 2 3 3 4
Output
YES
----------------------------------------------------------------------------------------------------
F. Julia the snail
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
8
4
1 2
3 4
2 5
6 7
5
1 2
1 4
1 6
2 7
6 8
Output
2
2
5
5
7
Input
10
10
3 7
1 4
1 6
5 5
1 1
3 9
7 8
1 2
3 3
7 10
10
2 4
1 7
3 4
3 5
2 8
2 5
5 5
3 5
7 7
3 10
Output
2
7
3
3
2
2
5
3
7
10
----------------------------------------------------------------------------------------------------
G. Oleg and chess
time limit per test: 6.5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
5
1 1 2 1
1 3 1 5
4 1 5 5
2 5 2 5
3 2 3 5
Output
3
Input
8
4
2 2 4 6
1 8 1 8
7 1 8 2
5 4 6 8
Output
8
----------------------------------------------------------------------------------------------------
