Codeforces Round 635 (Div. 1)


A. Linova and Kingdom
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7 4
1 2
1 3
1 4
3 5
3 6
4 7
Output
7
Input
4 1
1 2
1 3
2 4
Output
2
Input
8 5
7 5
1 7
6 1
3 7
8 3
2 1
4 5
Output
9
----------------------------------------------------------------------------------------------------
B. Xenia and Colorful Gems
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
2 2 3
7 8
6 3
3 1 4
1 1 1
1
1
1000000000
2 2 2
1 2
5 4
6 7
2 2 2
1 2
3 4
6 7
3 4 1
3 2 1
7 3 3 4
6
Output
14
1999999996000000002
24
24
14
----------------------------------------------------------------------------------------------------
C. Kaavi and Magic Spell
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
abab
ba
Output
12
Input
defineintlonglong
signedmain
Output
0
Input
rotator
rotator
Output
4
Input
cacdcdbbbb
bdcaccdbbb
Output
24
----------------------------------------------------------------------------------------------------
D. Yui and Mahjong Set
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
1 6
2 9
5 12
5 24
6 24
Output
+ 1
+ 1
+ 2
+ 5
! 2 1 3 0 2
----------------------------------------------------------------------------------------------------
E1. Chiori and Doll Picking (easy version)
time limit per test: 3 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
4 4
3 5 8 14
Output
2 2 6 6 0 
Input
6 7
11 45 14 9 19 81
Output
1 2 11 20 15 10 5 0 
----------------------------------------------------------------------------------------------------
E2. Chiori and Doll Picking (hard version)
time limit per test: 3 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
4 4
3 5 8 14
Output
2 2 6 6 0 
Input
6 7
11 45 14 9 19 81
Output
1 2 11 20 15 10 5 0 
----------------------------------------------------------------------------------------------------
F. Journey
time limit per test: 4 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
8 4 1
1 7
1 2
2 5
4 6
6 3
6 2
6 8
7 8
3 8
2 6
4 1
Output
4
Input
10 4 2
3 10
9 3
4 9
4 6
8 2
1 7
2 1
4 5
6 7
7 1
8 7
9 2
10 3
Output
1
Input
13 8 3
7 6
9 11
5 6
11 3
9 7
2 12
4 3
1 2
5 8
6 13
5 10
3 1
10 4
10 11
8 11
4 9
2 5
3 5
7 3
8 10
Output
14
----------------------------------------------------------------------------------------------------
