CodeEff/ECCO huggingface dataset:
Problem Description: Score : 100 points
Problem Statement
On some day in January
2018
, Takaki is writing a document. The document has a column where the current date is written in
yyyy/mm/dd
format. For example, January
23
,
2018
should be written as
2018/01/23
.
After finishing the document, she noticed that she had mistakenly wrote
2017
at the beginning of the date column. Write a program that, when the string that Takaki wrote in the date column,
S
, is given as input, modifies the first four characters in
S
to
2018
and prints it.
Constraints
S
is a string of length
10
.
The first eight characters in
S
are
2017/01/
.
The last two characters in
S
are digits and represent an integer between
1
and
31
(inclusive).
Input
Input is given from Standard Input in the following format:
S
Output
Replace the first four characters in
S
with
2018
and print it.
Sample Input 1
2017/01/07
Sample Output 1
2018/01/07
Sample Input 2
2017/01/31
Sample Output 2
2018/01/31
Problem Description: Score : 400 points
Problem Statement
You are going out for a walk, when you suddenly encounter a monster. Fortunately, you have
N
katana (swords), Katana
1
, Katana
2
,
…
, Katana
N
, and can perform the following two kinds of attacks in any order:
Wield one of the katana you have. When you wield Katana
i
(1 ≤ i ≤ N)
, the monster receives
a_i
points of damage. The same katana can be wielded any number of times.
Throw one of the katana you have. When you throw Katana
i
(1 ≤ i ≤ N)
at the monster, it receives
b_i
points of damage, and you lose the katana. That is, you can no longer wield or throw that katana.
The monster will vanish when the total damage it has received is
H
points or more. At least how many attacks do you need in order to vanish it in total?
Constraints
1 ≤ N ≤ 10^5
1 ≤ H ≤ 10^9
1 ≤ a_i ≤ b_i ≤ 10^9
All input values are integers.
Input
Input is given from Standard Input in the following format:
N
H
a_1
b_1
:
a_N
b_N
Output
Print the minimum total number of attacks required to vanish the monster.
Sample Input 1
1 10
3 5
Sample Output 1
3
You have one katana. Wielding it deals
3
points of damage, and throwing it deals
5
points of damage. By wielding it twice and then throwing it, you will deal
3 + 3 + 5 = 11
points of damage in a total of three attacks, vanishing the monster.
Sample Input 2
2 10
3 5
2 6
Sample Output 2
2
In addition to the katana above, you also have another katana. Wielding it deals
2
points of damage, and throwing it deals
6
points of damage. By throwing both katana, you will deal
5 + 6 = 11
points of damage in two attacks, vanishing the monster.
Sample Input 3
4 1000000000
1 1
1 10000000
1 30000000
1 99999999
Sample Output 3
860000004
Sample Input 4
5 500
35 44
28 83
46 62
31 79
40 43
Sample Output 4
9
Problem Description: Score : 100 points
Problem Statement
How many hours do we have until New Year at
M
o'clock (24-hour notation) on
30
th, December?
Constraints
1≤M≤23
M
is an integer.
Input
Input is given from Standard Input in the following format:
M
Output
If we have
x
hours until New Year at
M
o'clock on
30
th, December, print
x
.
Sample Input 1
21
Sample Output 1
27
We have
27
hours until New Year at
21
o'clock on
30
th, December.
Sample Input 2
12
Sample Output 2
36
Problem Description: Score : 200 points
Problem Statement
The postal code in Atcoder Kingdom is
A+B+1
characters long, its
(A+1)
-th character is a hyphen
-
, and the other characters are digits from
0
through
9
.
You are given a string
S
. Determine whether it follows the postal code format in Atcoder Kingdom.
Constraints
1≤A,B≤5
|S|=A+B+1
S
consists of
-
and digits from
0
through
9
.
Input
Input is given from Standard Input in the following format:
A
B
S
Output
Print
Yes
if
S
follows the postal code format in AtCoder Kingdom; print
No
otherwise.
Sample Input 1
3 4
269-6650
Sample Output 1
Yes
The
(A+1)
-th character of
S
is
-
, and the other characters are digits from
0
through
9
, so it follows the format.
Sample Input 2
1 1
---
Sample Output 2
No
S
contains unnecessary
-
s other than the
(A+1)
-th character, so it does not follow the format.
Sample Input 3
1 2
7444
Sample Output 3
No
Problem Description: Score : 400 points
Problem Statement
We say that a odd number
N
is
similar to 2017
when both
N
and
(N+1)/2
are prime.
You are given
Q
queries.
In the
i
-th query, given two odd numbers
l_i
and
r_i
, find the number of odd numbers
x
similar to 2017 such that
l_i ≤ x ≤ r_i
.
Constraints
1≤Q≤10^5
1≤l_i≤r_i≤10^5
l_i
and
r_i
are odd.
All input values are integers.
Input
Input is given from Standard Input in the following format:
Q
l_1
r_1
:
l_Q
r_Q
Output
Print
Q
lines. The
i
-th line
(1≤i≤Q)
should contain the response to the
i
-th query.
Sample Input 1
1
3 7
Sample Output 1
2
3
is similar to 2017, since both
3
and
(3+1)/2=2
are prime.
5
is similar to 2017, since both
5
and
(5+1)/2=3
are prime.
7
is not similar to 2017, since
(7+1)/2=4
is not prime, although
7
is prime.
Thus, the response to the first query should be
2
.
Sample Input 2
4
13 13
7 11
7 11
2017 2017
Sample Output 2
1
0
0
1
Note that
2017
is also similar to 2017.
Sample Input 3
6
1 53
13 91
37 55
19 51
73 91
13 49
Sample Output 3
4
4
1
1
1
2
Problem Description: Score : 200 points
Problem Statement
Find the sum of the integers between
1
and
N
(inclusive), whose sum of digits written in base
10
is between
A
and
B
(inclusive).
Constraints
1 \leq N \leq 10^4
1 \leq A \leq B \leq 36
All input values are integers.
Input
Input is given from Standard Input in the following format:
N
A
B
Output
Print the sum of the integers between
1
and
N
(inclusive), whose sum of digits written in base
10
is between
A
and
B
(inclusive).
Sample Input 1
20 2 5
Sample Output 1
84
Among the integers not greater than
20
, the ones whose sums of digits are between
2
and
5
, are:
2,3,4,5,11,12,13,14
and
20
. We should print the sum of these,
84
.
Sample Input 2
10 1 2
Sample Output 2
13
Sample Input 3
100 4 16
Sample Output 3
4554
Problem Description: Score : 300 points
Problem Statement
As a token of his gratitude, Takahashi has decided to give his mother an integer sequence.
The sequence
A
needs to satisfy the conditions below:
A
consists of integers between
X
and
Y
(inclusive).
For each
1\leq i \leq |A|-1
,
A_{i+1}
is a multiple of
A_i
and strictly greater than
A_i
.
Find the maximum possible length of the sequence.
Constraints
1 \leq X \leq Y \leq 10^{18}
All input values are integers.
Input
Input is given from Standard Input in the following format:
X
Y
Output
Print the maximum possible length of the sequence.
Sample Input 1
3 20
Sample Output 1
3
The sequence
3,6,18
satisfies the conditions.
Sample Input 2
25 100
Sample Output 2
3
Sample Input 3
314159265 358979323846264338
Sample Output 3
31
Problem Description: Score : 500 points
Problem Statement
You are given a string
S
consisting of
0
and
1
.
Find the maximum integer
K
not greater than
|S|
such that we can turn all the characters of
S
into
0
by repeating the following operation some number of times.
Choose a contiguous segment
[l,r]
in
S
whose length is at least
K
(that is,
r-l+1\geq K
must be satisfied). For each integer
i
such that
l\leq i\leq r
, do the following: if
S_i
is
0
, replace it with
1
; if
S_i
is
1
, replace it with
0
.
Constraints
1\leq |S|\leq 10^5
S_i(1\leq i\leq N)
is either
0
or
1
.
Input
Input is given from Standard Input in the following format:
S
Output
Print the maximum integer
K
such that we can turn all the characters of
S
into
0
by repeating the operation some number of times.
Sample Input 1
010
Sample Output 1
2
We can turn all the characters of
S
into
0
by the following operations:
Perform the operation on the segment
S[1,3]
with length
3
.
S
is now
101
.
Perform the operation on the segment
S[1,2]
with length
2
.
S
is now
011
.
Perform the operation on the segment
S[2,3]
with length
2
.
S
is now
000
.
Sample Input 2
100000000
Sample Output 2
8
Sample Input 3
00001111
Sample Output 3
4
Problem Description: Score : 800 points
Problem Statement
You are given a string
S
consisting of lowercase English letters.
Determine whether we can turn
S
into a palindrome by repeating the operation of swapping two adjacent characters. If it is possible, find the minimum required number of operations.
Constraints
1 \leq |S| \leq 2 × 10^5
S
consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S
Output
If we cannot turn
S
into a palindrome, print
-1
. Otherwise, print the minimum required number of operations.
Sample Input 1
eel
Sample Output 1
1
We can turn
S
into a palindrome by the following operation:
Swap the
2
-nd and
3
-rd characters.
S
is now
ele
.
Sample Input 2
ataatmma
Sample Output 2
4
We can turn
S
into a palindrome by the following operation:
Swap the
5
-th and
6
-th characters.
S
is now
ataamtma
.
Swap the
4
-th and
5
-th characters.
S
is now
atamatma
.
Swap the
3
-rd and
4
-th characters.
S
is now
atmaatma
.
Swap the
2
-nd and
3
-rd characters.
S
is now
amtaatma
.
Sample Input 3
snuke
Sample Output 3
-1
We cannot turn
S
into a palindrome.
Problem Description: Score : 100 points
Problem Statement
You are given two positive integers
a
and
b
.
Let
x
be the average of
a
and
b
.
Print
x
rounded up to the nearest integer.
Constraints
a
and
b
are integers.
1 \leq a, b \leq 100
Input
Input is given from Standard Input in the following format:
a
b
Output
Print
x
rounded up to the nearest integer.
Sample Input 1
1 3
Sample Output 1
2
The average of
1
and
3
is
2.0
, and it will be rounded up to the nearest integer,
2
.
Sample Input 2
7 4
Sample Output 2
6
The average of
7
and
4
is
5.5
, and it will be rounded up to the nearest integer,
6
.
Sample Input 3
5 5
Sample Output 3
5
Problem Description: Score : 200 points
Problem Statement
You are given strings
s
and
t
, consisting of lowercase English letters.
You will create a string
s'
by freely rearranging the characters in
s
.
You will also create a string
t'
by freely rearranging the characters in
t
.
Determine whether it is possible to satisfy
s' < t'
for the lexicographic order.
Notes
For a string
a = a_1 a_2 ... a_N
of length
N
and a string
b = b_1 b_2 ... b_M
of length
M
, we say
a < b
for the lexicographic order if either one of the following two conditions holds true:
N < M
and
a_1 = b_1
,
a_2 = b_2
, ...,
a_N = b_N
.
There exists
i
(
1 \leq i \leq N, M
) such that
a_1 = b_1
,
a_2 = b_2
, ...,
a_{i - 1} = b_{i - 1}
and
a_i < b_i
. Here, letters are compared using alphabetical order.
For example,
xy
<
xya
and
atcoder
<
atlas
.
Constraints
The lengths of
s
and
t
are between
1
and
100
(inclusive).
s
and
t
consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
s
t
Output
If it is possible to satisfy
s' < t'
, print
Yes
; if it is not, print
No
.
Sample Input 1
yx
axy
Sample Output 1
Yes
We can, for example, rearrange
yx
into
xy
and
axy
into
yxa
. Then,
xy
<
yxa
.
Sample Input 2
ratcode
atlas
Sample Output 2
Yes
We can, for example, rearrange
ratcode
into
acdeort
and
atlas
into
tslaa
. Then,
acdeort
<
tslaa
.
Sample Input 3
cd
abc
Sample Output 3
No
No matter how we rearrange
cd
and
abc
, we cannot achieve our objective.
Sample Input 4
w
ww
Sample Output 4
Yes
Sample Input 5
zzz
zzz
Sample Output 5
No
Problem Description: Score : 300 points
Problem Statement
You are given a sequence of positive integers of length
N
,
a = (a_1, a_2, ..., a_N)
.
Your objective is to remove some of the elements in
a
so that
a
will be a
good sequence
.
Here, an sequence
b
is a
good sequence
when the following condition holds true:
For each element
x
in
b
, the value
x
occurs exactly
x
times in
b
.
For example,
(3, 3, 3)
,
(4, 2, 4, 1, 4, 2, 4)
and
()
(an empty sequence) are good sequences, while
(3, 3, 3, 3)
and
(2, 4, 1, 4, 2)
are not.
Find the minimum number of elements that needs to be removed so that
a
will be a good sequence.
Constraints
1 \leq N \leq 10^5
a_i
is an integer.
1 \leq a_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N
a_1
a_2
...
a_N
Output
Print the minimum number of elements that needs to be removed so that
a
will be a good sequence.
Sample Input 1
4
3 3 3 3
Sample Output 1
1
We can, for example, remove one occurrence of
3
. Then,
(3, 3, 3)
is a good sequence.
Sample Input 2
5
2 4 1 4 2
Sample Output 2
2
We can, for example, remove two occurrences of
4
. Then,
(2, 1, 2)
is a good sequence.
Sample Input 3
6
1 2 2 3 3 3
Sample Output 3
0
Sample Input 4
1
1000000000
Sample Output 4
1
Remove one occurrence of
10^9
. Then,
()
is a good sequence.
Sample Input 5
8
2 7 1 8 2 8 1 8
Sample Output 5
5
Problem Description: Score : 500 points
Problem Statement
A robot is put at the origin in a two-dimensional plane.
Initially, the robot is facing in the positive
x
-axis direction.
This robot will be given an instruction sequence
s
.
s
consists of the following two kinds of letters, and will be executed in order from front to back.
F
: Move in the current direction by distance
1
.
T
: Turn
90
degrees, either clockwise or counterclockwise.
The objective of the robot is to be at coordinates
(x, y)
after all the instructions are executed.
Determine whether this objective is achievable.
Constraints
s
consists of
F
and
T
.
1 \leq |s| \leq 8
000
x
and
y
are integers.
|x|, |y| \leq |s|
Input
Input is given from Standard Input in the following format:
s
x
y
Output
If the objective is achievable, print
Yes
; if it is not, print
No
.
Sample Input 1
FTFFTFFF
4 2
Sample Output 1
Yes
The objective can be achieved by, for example, turning counterclockwise in the first
T
and turning clockwise in the second
T
.
Sample Input 2
FTFFTFFF
-2 -2
Sample Output 2
Yes
The objective can be achieved by, for example, turning clockwise in the first
T
and turning clockwise in the second
T
.
Sample Input 3
FF
1 0
Sample Output 3
No
Sample Input 4
TF
1 0
Sample Output 4
No
Sample Input 5
FFTTFF
0 0
Sample Output 5
Yes
The objective can be achieved by, for example, turning counterclockwise in the first
T
and turning counterclockwise in the second
T
.
Sample Input 6
TTTT
1 0
Sample Output 6
No
Problem Description: Score : 700 points
Problem Statement
For strings
s
and
t
, we will say that
s
and
t
are
prefix-free
when neither is a prefix of the other.
Let
L
be a positive integer. A set of strings
S
is a
good string set
when the following conditions hold true:
Each string in
S
has a length between
1
and
L
(inclusive) and consists of the characters
0
and
1
.
Any two distinct strings in
S
are prefix-free.
We have a good string set
S = \{ s_1, s_2, ..., s_N \}
. Alice and Bob will play a game against each other. They will alternately perform the following operation, starting from Alice:
Add a new string to
S
. After addition,
S
must still be a good string set.
The first player who becomes unable to perform the operation loses the game. Determine the winner of the game when both players play optimally.
Constraints
1 \leq N \leq 10^5
1 \leq L \leq 10^{18}
s_1
,
s_2
, ...,
s_N
are all distinct.
{
s_1
,
s_2
, ...,
s_N
} is a good string set.
|s_1| + |s_2| + ... + |s_N| \leq 10^5
Input
Input is given from Standard Input in the following format:
N
L
s_1
s_2
:
s_N
Output
If Alice will win, print
Alice
; if Bob will win, print
Bob
.
Sample Input 1
2 2
00
01
Sample Output 1
Alice
If Alice adds
1
, Bob will be unable to add a new string.
Sample Input 2
2 2
00
11
Sample Output 2
Bob
There are two strings that Alice can add on the first turn:
01
and
10
.
In case she adds
01
, if Bob add
10
, she will be unable to add a new string.
Also, in case she adds
10
, if Bob add
01
, she will be unable to add a new string.
Sample Input 3
3 3
0
10
110
Sample Output 3
Alice
If Alice adds
111
, Bob will be unable to add a new string.
Sample Input 4
2 1
0
1
Sample Output 4
Bob
Alice is unable to add a new string on the first turn.
Sample Input 5
1 2
11
Sample Output 5
Alice
Sample Input 6
2 3
101
11
Sample Output 6
Bob
Problem Description: Score : 800 points
Problem Statement
There is a tree with
N
vertices. The vertices are numbered
1
through
N
. The
i
-th edge (
1 \leq i \leq N - 1
) connects Vertex
x_i
and
y_i
. For vertices
v
and
w
(
1 \leq v, w \leq N
), we will define the distance between
v
and
w
d(v, w)
as "the number of edges contained in the path
v
-
w
".
A squirrel lives in each vertex of the tree. They are planning to move, as follows. First, they will freely choose a permutation of
(1, 2, ..., N)
,
p = (p_1, p_2, ..., p_N)
. Then, for each
1 \leq i \leq N
, the squirrel that lived in Vertex
i
will move to Vertex
p_i
.
Since they like long travels, they have decided to maximize the total distance they traveled during the process. That is, they will choose
p
so that
d(1, p_1) + d(2, p_2) + ... + d(N, p_N)
will be maximized. How many such ways are there to choose
p
, modulo
10^9 + 7
?
Constraints
2 \leq N \leq 5,000
1 \leq x_i, y_i \leq N
The input graph is a tree.
Input
Input is given from Standard Input in the following format:
N
x_1
y_1
x_2
y_2
:
x_{N - 1}
y_{N - 1}
Output
Print the number of the ways to choose
p
so that the condition is satisfied, modulo
10^9 + 7
.
Sample Input 1
3
1 2
2 3
Sample Output 1
3
The maximum possible distance traveled by squirrels is
4
.
There are three choices of
p
that achieve it, as follows:
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
Sample Input 2
4
1 2
1 3
1 4
Sample Output 2
11
The maximum possible distance traveled by squirrels is
6
.
For example,
p = (2, 1, 4, 3)
achieves it.
Sample Input 3
6
1 2
1 3
1 4
2 5
2 6
Sample Output 3
36
Sample Input 4
7
1 2
6 3
4 5
1 7
1 5
2 3
Sample Output 4
396
Problem Description: Score : 300 points
Problem Statement
Takahashi has
N
balls. Initially, an integer
A_i
is written on the
i
-th ball.
He would like to rewrite the integer on some balls so that there are at most
K
different integers written on the
N
balls.
Find the minimum number of balls that Takahashi needs to rewrite the integers on them.
Constraints
1 \leq K \leq N \leq 200000
1 \leq A_i \leq N
All input values are integers.
Input
Input is given from Standard Input in the following format:
N
K
A_1
A_2
...
A_N
Output
Print the minimum number of balls that Takahashi needs to rewrite the integers on them.
Sample Input 1
5 2
1 1 2 2 5
Sample Output 1
1
For example, if we rewrite the integer on the fifth ball to
2
, there are two different integers written on the balls:
1
and
2
.
On the other hand, it is not possible to rewrite the integers on zero balls so that there are at most two different integers written on the balls, so we should print
1
.
Sample Input 2
4 4
1 1 2 2
Sample Output 2
0
Already in the beginning, there are two different integers written on the balls, so we do not need to rewrite anything.
Sample Input 3
10 3
5 1 3 2 4 1 1 2 3 4
Sample Output 3
3
Problem Description: Score : 1000 points
Problem Statement
Snuke has a rooted tree with
N+1
vertices.
The vertices are numbered
0
through
N
, and Vertex
0
is the root of the tree.
The parent of Vertex
i
(1 \leq i \leq N)
is Vertex
p_i
.
Besides this tree, Snuke also has an box which is initially empty and many marbles, and playing with them.
The play begins with placing one marble on some of the vertices, then proceeds as follows:
If there is a marble on Vertex
0
, move the marble into the box.
Move each marble from the vertex to its parent (all at once).
For each vertex occupied by two or more marbles, remove all the marbles from the vertex.
If there exists a vertex with some marbles, go to Step 1. Otherwise, end the play.
There are
2^{N+1}
ways to place marbles on some of the vertices.
For each of them, find
the number of marbles that will be in the box at the end of the play
, and compute the sum of all those numbers modulo
1,000,000,007
.
Constraints
1 \leq N < 2 \times 10^{5}
0 \leq p_i < i
Partial Scores
In the test set worth
400
points,
N < 2{,}000
.
Input
Input is given from Standard Input in the following format:
N
p_1
p_2
...
p_{N}
Output
Print the answer.
Sample Input 1
2
0 0
Sample Output 1
8
When we place a marble on both Vertex
1
and
2
, there will be multiple marbles on Vertex
0
by step 2. In such a case, these marbles will be removed instead of being moved to the box.
Sample Input 2
5
0 1 1 0 4
Sample Output 2
96
Sample Input 3
31
0 1 0 2 4 0 4 1 6 4 3 9 7 3 7 2 15 6 12 10 12 16 5 3 20 1 25 20 23 24 23
Sample Output 3
730395550
Be sure to compute the sum modulo
1,000,000,007
.
Problem Description: Score : 100 points
Problem Statement
You are parking at a parking lot. You can choose from the following two fee plans:
Plan
1
: The fee will be
A×T
yen (the currency of Japan) when you park for
T
hours.
Plan
2
: The fee will be
B
yen, regardless of the duration.
Find the minimum fee when you park for
N
hours.
Constraints
1≤N≤20
1≤A≤100
1≤B≤2000
All input values are integers.
Input
Input is given from Standard Input in the following format:
N
A
B
Output
When the minimum fee is
x
yen, print the value of
x
.
Sample Input 1
7 17 120
Sample Output 1
119
If you choose Plan
1
, the fee will be
7×17=119
yen.
If you choose Plan
2
, the fee will be
120
yen.
Thus, the minimum fee is
119
yen.
Sample Input 2
5 20 100
Sample Output 2
100
The fee might be the same in the two plans.
Sample Input 3
6 18 100
Sample Output 3
100
Problem Description: Score : 200 points
Problem Statement
An integer
X
is called a Harshad number if
X
is divisible by
f(X)
, where
f(X)
is the sum of the digits in
X
when written in base
10
.
Given an integer
N
, determine whether it is a Harshad number.
Constraints
1?N?10^8
N
is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print
Yes
if
N
is a Harshad number; print
No
otherwise.
Sample Input 1
12
Sample Output 1
Yes
f(12)=1+2=3
. Since
12
is divisible by
3
,
12
is a Harshad number.
Sample Input 2
57
Sample Output 2
No
f(57)=5+7=12
. Since
57
is not divisible by
12
,
12
is not a Harshad number.
Sample Input 3
148
Sample Output 3
No
Problem Description: Score : 300 points
Problem Statement
Joisino is planning to open a shop in a shopping street.
Each of the five weekdays is divided into two periods, the morning and the evening. For each of those ten periods, a shop must be either open during the whole period, or closed during the whole period. Naturally, a shop must be open during at least one of those periods.
There are already
N
stores in the street, numbered
1
through
N
.
You are given information of the business hours of those shops,
F_{i,j,k}
. If
F_{i,j,k}=1
, Shop
i
is open during Period
k
on Day
j
(this notation is explained below); if
F_{i,j,k}=0
, Shop
i
is closed during that period. Here, the days of the week are denoted as follows. Monday: Day
1
, Tuesday: Day
2
, Wednesday: Day
3
, Thursday: Day
4
, Friday: Day
5
. Also, the morning is denoted as Period
1
, and the afternoon is denoted as Period
2
.
Let
c_i
be the number of periods during which both Shop
i
and Joisino's shop are open. Then, the profit of Joisino's shop will be
P_{1,c_1}+P_{2,c_2}+...+P_{N,c_N}
.
Find the maximum possible profit of Joisino's shop when she decides whether her shop is open during each period, making sure that it is open during at least one period.
Constraints
1≤N≤100
0≤F_{i,j,k}≤1
For every integer
i
such that
1≤i≤N
, there exists at least one pair
(j,k)
such that
F_{i,j,k}=1
.
-10^7≤P_{i,j}≤10^7
All input values are integers.
Input
Input is given from Standard Input in the following format:
N
F_{1,1,1}
F_{1,1,2}
...
F_{1,5,1}
F_{1,5,2}
:
F_{N,1,1}
F_{N,1,2}
...
F_{N,5,1}
F_{N,5,2}
P_{1,0}
...
P_{1,10}
:
P_{N,0}
...
P_{N,10}
Output
Print the maximum possible profit of Joisino's shop.
Sample Input 1
1
1 1 0 1 0 0 0 1 0 1
3 4 5 6 7 8 9 -2 -3 4 -2
Sample Output 1
8
If her shop is open only during the periods when Shop
1
is opened, the profit will be
8
, which is the maximum possible profit.
Sample Input 2
2
1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 1 1
0 -2 -2 -2 -2 -2 -1 -1 -1 -1 -1
0 -2 -2 -2 -2 -2 -1 -1 -1 -1 -1
Sample Output 2
-2
Note that a shop must be open during at least one period, and the profit may be negative.
Sample Input 3
3
1 1 1 1 1 1 0 0 1 1
0 1 0 1 1 1 1 0 1 0
1 0 1 1 0 1 0 1 0 1
-8 6 -2 -8 -8 4 8 7 -6 2 2
-9 2 0 1 7 -5 0 -2 -6 5 5
6 -6 7 -9 6 -5 8 0 -9 -7 -7
Sample Output 3
23