Good Bye 2016


A. New Year and Hurry
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 222
Output
2
Input
4 190
Output
4
Input
7 1
Output
7
----------------------------------------------------------------------------------------------------
B. New Year and North Pole
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
7500 South
10000 East
3500 North
4444 West
4000 North
Output
YES
Input
2
15000 South
4000 East
Output
NO
Input
5
20000 South
1000 North
1000000 West
9000 North
10000 North
Output
YES
Input
3
20000 South
10 East
20000 North
Output
NO
Input
2
1000 North
1000 South
Output
NO
Input
4
50 South
50 North
15000 South
15000 North
Output
YES
----------------------------------------------------------------------------------------------------
C. New Year and Rating
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
-7 1
5 2
8 2
Output
1907
Input
2
57 1
22 2
Output
Impossible
Input
1
-5 1
Output
Infinity
Input
4
27 2
13 1
-50 1
8 2
Output
1897
----------------------------------------------------------------------------------------------------
D. New Year and Fireworks
time limit per test: 2.5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
4 2 2 3
Output
39
Input
6
1 1 1 1 1 3
Output
85
Input
1
3
Output
3
----------------------------------------------------------------------------------------------------
E. New Year and Old Subsequence
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
8 3
20166766
1 8
1 7
2 8
Output
4
3
-1
Input
15 5
012016662091670
3 4
1 14
4 15
1 13
10 15
Output
-1
2
1
-1
-1
Input
4 2
1234
2 4
1 2
Output
-1
-1
----------------------------------------------------------------------------------------------------
F. New Year and Finding Roots
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
1
3
3
4 5 7
2
1 2
1
2
Output
? 1
? 5
? 6
! 5
Input
2
2
1
3
2
1 2
2
1 2
4
3
3 12 13
Output
? 1
? 3
? 3
! 3
? 6
! 1
----------------------------------------------------------------------------------------------------
G. New Year and Binary Tree Paths
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
10
Output
4
----------------------------------------------------------------------------------------------------
H. New Year and Snowy Grid
time limit per test: 9 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 5 4
.....
.....
.#...
1
1 4
1
1 5
2
2 4
3 1
2
1 5
3 3
Output
NO
YES
YES
NO
Input
9 31 5
...............................
...............................
.###.###.#.###...###.###.#.###.
...#.#.#.#.#.......#.#.#.#...#.
.###.#.#.#.###...###.#.#.#...#.
.#...#.#.#.#.#...#...#.#.#...#.
.###.###.#.###...###.###.#...#.
...............................
...............................
5
6 5
2 11
1 14
8 15
2 14
5
2 14
1 14
8 16
6 5
2 11
3
2 2
1 4
8 30
10
3 1
3 11
5 16
7 21
4 16
3 5
7 31
3 9
7 25
3 27
10
3 1
3 9
7 25
3 27
7 21
4 17
3 5
7 31
4 16
3 11
Output
NO
YES
YES
YES
NO
----------------------------------------------------------------------------------------------------
