VK Cup 2017 - Finals


A. High Load
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3 2
Output
2
1 2
2 3
Input
5 3
Output
3
1 2
2 3
3 4
3 5
----------------------------------------------------------------------------------------------------
B. DNA Evolution
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
ATGCATGC
4
2 1 8 ATGC
2 2 6 TTT
1 4 T
2 2 6 TA
Output
8
2
4
Input
GAGTTGTTAA
6
2 3 4 TATGGTG
1 1 T
1 6 G
2 5 9 AGTAATA
1 10 G
2 2 6 TTGT
Output
0
3
1
----------------------------------------------------------------------------------------------------
C. Bamboo Partition
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3 4
1 3 5
Output
3
Input
3 40
10 30 50
Output
32
----------------------------------------------------------------------------------------------------
D. Rusty String
time limit per test: 3 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
 
5
V??VK
 
6
??????
 
4
?VK?
Output
2
3 5
6
1 2 3 4 5 6
3
2 3 4
----------------------------------------------------------------------------------------------------
E. Singer House
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
2
Output
9
Input
3
Output
245
Input
20
Output
550384565
----------------------------------------------------------------------------------------------------
F. Perpetual Motion Machine
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
4
 
4 4
1 2
2 3
3 4
4 2
 
3 2
2 3
3 1
 
4 6
1 2
3 4
4 2
1 4
1 3
3 2
 
10 9
2 1
3 2
5 2
6 2
2 7
2 8
2 9
2 10
4 2
Output
YES
1 2 2 1
NO
YES
1 1 1 1
YES
1 5 1 1 1 1 1 1 1 1
----------------------------------------------------------------------------------------------------
G. Dirty Arkady's Kitchen
time limit per test: 6 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
5 6
1 2 0 1
2 5 2 3
2 5 0 1
1 3 0 1
3 4 1 2
4 5 2 3
Output
3
Input
2 1
1 2 1 100
Output
-1
----------------------------------------------------------------------------------------------------
