Codeforces Round 602 (Div. 2, based on Technocup 2020 Elimination Round 3)


A. Math Problem
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
3
4 5
5 9
7 7
5
11 19
4 17
16 16
3 12
14 17
1
1 10
1
1 1
Output
2
4
0
0
----------------------------------------------------------------------------------------------------
B. Box
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
5
1 3 4 5 5
4
1 1 3 4
2
2 2
1
1
Output
1 3 4 5 2 
-1
2 1 
1 
----------------------------------------------------------------------------------------------------
C. Messy
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
8 2
()(())()
10 3
))()()()((
2 1
()
2 1
)(
Output
4
3 4
1 1
5 8
2 2
3
4 10
1 4
6 7
0
1
1 2
----------------------------------------------------------------------------------------------------
D1. Optimal Subsequences (Easy Version)
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
10 20 10
6
1 1
2 1
2 2
3 1
3 2
3 3
Output
20
10
20
10
20
10
Input
7
1 2 1 3 1 2 1
9
2 1
2 2
3 1
3 2
3 3
1 1
7 1
7 7
7 4
Output
2
3
2
3
2
3
1
1
3
----------------------------------------------------------------------------------------------------
D2. Optimal Subsequences (Hard Version)
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
10 20 10
6
1 1
2 1
2 2
3 1
3 2
3 3
Output
20
10
20
10
20
10
Input
7
1 2 1 3 1 2 1
9
2 1
2 2
3 1
3 2
3 3
1 1
7 1
7 7
7 4
Output
2
3
2
3
2
3
1
1
3
----------------------------------------------------------------------------------------------------
E. Arson In Berland Forest
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3 6
XXXXXX
XXXXXX
XXXXXX
Output
1
......
.X.XX.
......
Input
10 10
.XXXXXX...
.XXXXXX...
.XXXXXX...
.XXXXXX...
.XXXXXXXX.
...XXXXXX.
...XXXXXX.
...XXXXXX.
...XXXXXX.
..........
Output
2
..........
..........
...XX.....
..........
..........
..........
.....XX...
..........
..........
..........
Input
4 5
X....
..XXX
..XXX
..XXX
Output
0
X....
..XXX
..XXX
..XXX
----------------------------------------------------------------------------------------------------
F1. Wrong Answer on test 233 (Easy Version)
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 3
1 3 1
Output
9
Input
5 5
1 1 4 2 2
Output
1000
----------------------------------------------------------------------------------------------------
F2. Wrong Answer on test 233 (Hard Version)
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 3
1 3 1
Output
9
Input
5 5
1 1 4 2 2
Output
1000
Input
6 2
1 1 2 2 1 1
Output
16
----------------------------------------------------------------------------------------------------
