Codeforces Round 423 (Div. 2, rated, based on VK Cup Finals)


A. Restaurant Tables
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4 1 2
1 2 1 1
Output
0
Input
4 1 1
1 1 2 1
Output
2
----------------------------------------------------------------------------------------------------
B. Black Square
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5 4
WWWW
WWWB
WWWB
WWBB
WWWW
Output
5
Input
1 2
BB
Output
-1
Input
3 3
WWW
WWW
WWW
Output
1
----------------------------------------------------------------------------------------------------
C. String Reconstruction
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
a 4 1 3 5 7
ab 2 1 5
ca 1 4
Output
abacaba
Input
1
a 1 3
Output
aaa
Input
3
ab 1 1
aba 1 3
ab 2 3 5
Output
ababab
----------------------------------------------------------------------------------------------------
D. 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
----------------------------------------------------------------------------------------------------
E. 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
----------------------------------------------------------------------------------------------------
F. Best Edge Weight
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4 4
1 2 2
2 3 2
3 4 2
4 1 3
Output
2 2 2 1 
Input
4 3
1 2 2
2 3 2
3 4 2
Output
-1 -1 -1 
----------------------------------------------------------------------------------------------------
