CodeEff/ECCO huggingface dataset:
Problem Description: Score : 500 points
Problem Statement
There is a directed graph with
N
vertices numbered
1
to
N
and
M
edges.
The
i
-th edge is directed from Vertex
A_i
to Vertex
B_i
, and there are
C_i
coins placed along that edge.
Additionally, there is a button on Vertex
N
.
We will play a game on this graph.
You start the game on Vertex
1
with zero coins, and head for Vertex
N
by traversing the edges while collecting coins.
It takes one minute to traverse an edge, and you can collect the coins placed along the edge each time you traverse it.
As usual in games, even if you traverse an edge once and collect the coins, the same number of coins will reappear next time you traverse that edge, which you can collect again.
When you reach Vertex
N
, you can end the game by pressing the button. (You can also choose to leave Vertex
N
without pressing the button and continue traveling.)
However, when you end the game, you will be asked to pay
T \times P
coins, where
T
is the number of minutes elapsed since the start of the game. If you have less than
T \times P
coins, you will have to pay all of your coins instead.
Your score will be the number of coins you have after this payment.
Determine if there exists a maximum value of the score that can be obtained. If the answer is yes, find that maximum value.
Constraints
2 \leq N \leq 2500
1 \leq M \leq 5000
1 \leq A_i, B_i \leq N
1 \leq C_i \leq 10^5
0 \leq P \leq 10^5
All values in input are integers.
Vertex
N
can be reached from Vertex
1
.
Input
Input is given from Standard Input in the following format:
N
M
P
A_1
B_1
C_1
:
A_M
B_M
C_M
Output
If there exists a maximum value of the score that can be obtained, print that maximum value; otherwise, print
-1
.
Sample Input 1
3 3 10
1 2 20
2 3 30
1 3 45
Sample Output 1
35
There are two ways to travel from Vertex
1
to Vertex
3
:
Vertex
1 \rightarrow 2 \rightarrow 3
: You collect
20 + 30 = 50
coins on the way. After two minutes from the start of the game, you press the button, pay
2 \times 10 = 20
coins, and you have
50 - 20 = 30
coins left.
Vertex
1 \rightarrow 2
: You collect
45
coins on the way. After one minute from the start of the game, you press the button, pay
1 \times 10 = 10
coins, and you have
45 - 10 = 35
coins left.
Thus, the maximum score that can be obtained is
35
.
Sample Input 2
2 2 10
1 2 100
2 2 100
Sample Output 2
-1
The edge extending from Vertex
1
takes you to Vertex
2
. If you then traverse the edge extending from Vertex
2
to itself
t
times and press the button, your score will be
90 + 90t
. Thus, you can infinitely increase your score, which means there is no maximum value of the score that can be obtained.
Sample Input 3
4 5 10
1 2 1
1 4 1
3 4 1
2 2 100
3 3 100
Sample Output 3
0
There is no way to travel from Vertex
1
to Vertex
4
other than traversing the edge leading from Vertex
1
to Vertex
4
directly. You will pick up one coin along this edge, but after being asked to paying
10
coins, your score will be
0
.
Note that you can collect an infinite number of coins if you traverse the edge leading from Vertex
1
to Vertex
2
, but this is pointless since you can no longer reach Vertex
4
and end the game.
Problem Description: Score : 300 points
Problem Statement
You are given two non-negative integers
L
and
R
.
We will choose two integers
i
and
j
such that
L \leq i < j \leq R
.
Find the minimum possible value of
(i \times j) \mbox{ mod } 2019
.
Constraints
All values in input are integers.
0 \leq L < R \leq 2 \times 10^9
Input
Input is given from Standard Input in the following format:
L
R
Output
Print the minimum possible value of
(i \times j) \mbox{ mod } 2019
when
i
and
j
are chosen under the given condition.
Sample Input 1
2020 2040
Sample Output 1
2
When
(i, j) = (2020, 2021)
,
(i \times j) \mbox{ mod } 2019  = 2
.
Sample Input 2
4 5
Sample Output 2
20
We have only one choice:
(i, j) = (4, 5)
.
Problem Description: Score : 100 points
Problem Statement
Snuke has
N
integers:
1,2,\ldots,N
.
He will choose
K
of them and give those to Takahashi.
How many ways are there to choose
K
consecutive integers?
Constraints
All values in input are integers.
1 \leq K \leq N \leq 50
Input
Input is given from Standard Input in the following format:
N
K
Output
Print the answer.
Sample Input 1
3 2
Sample Output 1
2
There are two ways to choose two consecutive integers:
(1,2)
and
(2,3)
.
Sample Input 2
13 3
Sample Output 2
11
Problem Description: Score : 200 points
Problem Statement
There are
N
mountains ranging from east to west, and an ocean to the west.
At the top of each mountain, there is an inn. You have decided to choose where to stay from these inns.
The height of the
i
-th mountain from the west is
H_i
.
You can certainly see the ocean from the inn at the top of the westmost mountain.
For the inn at the top of the
i
-th mountain from the west
(i = 2, 3, ..., N)
, you can see the ocean if and only if
H_1 \leq H_i
,
H_2 \leq H_i
,
...
, and
H_{i-1} \leq H_i
.
From how many of these
N
inns can you see the ocean?
Constraints
All values in input are integers.
1 \leq N \leq 20
1 \leq H_i \leq 100
Input
Input is given from Standard Input in the following format:
N
H_1
H_2
...
H_N
Output
Print the number of inns from which you can see the ocean.
Sample Input 1
4
6 5 6 8
Sample Output 1
3
You can see the ocean from the first, third and fourth inns from the west.
Sample Input 2
5
4 5 3 5 4
Sample Output 2
3
Sample Input 3
5
9 5 6 8 4
Sample Output 3
1
Problem Description: Score : 200 points
Problem Statement
There are four towns, numbered
1,2,3
and
4
.
Also, there are three roads. The
i
-th road connects different towns
a_i
and
b_i
bidirectionally.
No two roads connect the same pair of towns. Other than these roads, there is no way to travel between these towns, but any town can be reached from any other town using these roads.
Determine if we can visit all the towns by traversing each of the roads exactly once.
Constraints
1 \leq a_i,b_i \leq 4(1\leq i\leq 3)
a_i
and
b_i
are different.
(1\leq i\leq 3)
No two roads connect the same pair of towns.
Any town can be reached from any other town using the roads.
Input
Input is given from Standard Input in the following format:
a_1
b_1
a_2
b_2
a_3
b_3
Output
If we can visit all the towns by traversing each of the roads exactly once, print
YES
; otherwise, print
NO
.
Sample Input 1
4 2
1 3
2 3
Sample Output 1
YES
We can visit all the towns in the order
1,3,2,4
.
Sample Input 2
3 2
2 4
1 2
Sample Output 2
NO
Sample Input 3
2 1
3 2
4 3
Sample Output 3
YES
Problem Description: Score : 200 points
Problem Statement
A sequence
a=\{a_1,a_2,a_3,......\}
is determined as follows:
The first term
s
is given as input.
Let
f(n)
be the following function:
f(n) = n/2
if
n
is even, and
f(n) = 3n+1
if
n
is odd.
a_i = s
when
i = 1
, and
a_i = f(a_{i-1})
when
i > 1
.
Find the minimum integer
m
that satisfies the following condition:
There exists an integer
n
such that
a_m = a_n (m > n)
.
Constraints
1 \leq s \leq 100
All values in input are integers.
It is guaranteed that all elements in
a
and the minimum
m
that satisfies the condition are at most
1000000
.
Input
Input is given from Standard Input in the following format:
s
Output
Print the minimum integer
m
that satisfies the condition.
Sample Input 1
8
Sample Output 1
5
a=\{8,4,2,1,4,2,1,4,2,1,......\}
. As
a_5=a_2
, the answer is
5
.
Sample Input 2
7
Sample Output 2
18
a=\{7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1,4,2,1,......\}
.
Sample Input 3
54
Sample Output 3
114
Problem Description: Score: 300 points
Problem Statement
In Republic of Atcoder, there are
N
prefectures, and a total of
M
cities that belong to those prefectures.
City
i
is established in year
Y_i
and belongs to Prefecture
P_i
.
You can assume that there are no multiple cities that are established in the same year.
It is decided to allocate a
12
-digit ID number to each city.
If City
i
is the
x
-th established city among the cities that belong to Prefecture
i
, the first six digits of the ID number of City
i
is
P_i
, and the last six digits of the ID number is
x
.
Here, if
P_i
or
x
(or both) has less than six digits, zeros are added to the left until it has six digits.
Find the ID numbers for all the cities.
Note that there can be a prefecture with no cities.
Constraints
1 \leq N \leq 10^5
1 \leq M \leq 10^5
1 \leq P_i \leq N
1 \leq Y_i \leq 10^9
Y_i
are all different.
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
M
P_1
Y_1
:
P_M
Y_M
Output
Print the ID numbers for all the cities, in ascending order of indices (City
1
, City
2
,
...
).
Sample Input 1
2 3
1 32
2 63
1 12
Sample Output 1
000001000002
000002000001
000001000001
As City
1
is the second established city among the cities that belong to Prefecture
1
, its ID number is
000001000002
.
As City
2
is the first established city among the cities that belong to Prefecture
2
, its ID number is
000002000001
.
As City
3
is the first established city among the cities that belong to Prefecture
1
, its ID number is
000001000001
.
Sample Input 2
2 3
2 55
2 77
2 99
Sample Output 2
000002000001
000002000002
000002000003
Problem Description: Score : 1100 points
Problem Statement
Let us consider a grid of squares with
10^9
rows and
N
columns. Let
(i, j)
be the square at the
i
-th column
(1 \leq i \leq N)
from the left and
j
-th row
(1 \leq j \leq 10^9)
from the bottom.
Snuke has cut out some part of the grid so that, for each
i = 1, 2, ..., N
, the bottom-most
h_i
squares are remaining in the
i
-th column from the left.
Now, he will paint the remaining squares in red and blue.
Find the number of the ways to paint the squares so that the following condition is satisfied:
Every remaining square is painted either red or blue.
For all
1 \leq i \leq N-1
and
1 \leq j \leq min(h_i, h_{i+1})-1
, there are exactly two squares painted red and two squares painted blue among the following four squares:
(i, j), (i, j+1), (i+1, j)
and
(i+1, j+1)
.
Since the number of ways can be extremely large, print the count modulo
10^9+7
.
Constraints
1 \leq N \leq 100
1 \leq h_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N
h_1
h_2
...
h_N
Output
Print the number of the ways to paint the squares, modulo
10^9+7
.
Sample Input 1
9
2 3 5 4 1 2 4 2 1
Sample Output 1
12800
One of the ways to paint the squares is shown below:
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
Sample Input 2
2
2 2
Sample Output 2
6
There are six ways to paint the squares, as follows:
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
Sample Input 3
5
2 1 2 1 2
Sample Output 3
256
Every way to paint the squares satisfies the condition.
Sample Input 4
9
27 18 28 18 28 45 90 45 23
Sample Output 4
844733013
Remember to print the number of ways modulo
10^9 + 7
.
Problem Description: Score : 500 points
Problem Statement
You are given a sequence
(P_1,P_2,...,P_N)
which is a permutation of the integers from
1
through
N
.
You would like to sort this sequence in ascending order by repeating the following operation:
Choose an element in the sequence and move it to the beginning or the end of the sequence.
Find the minimum number of operations required.
It can be proved that it is actually possible to sort the sequence using this operation.
Constraints
1 \leq N \leq 2\times 10^5
(P_1,P_2,...,P_N)
is a permutation of
(1,2,...,N)
.
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
P_1
:
P_N
Output
Print the minimum number of operations required.
Sample Input 1
4
1
3
2
4
Sample Output 1
2
For example, the sequence can be sorted in ascending order as follows:
Move
2
to the beginning. The sequence is now
(2,1,3,4)
.
Move
1
to the beginning. The sequence is now
(1,2,3,4)
.
Sample Input 2
6
3
2
5
1
4
6
Sample Output 2
4
Sample Input 3
8
6
3
1
2
7
4
8
5
Sample Output 3
5
Problem Description: Score: 100 points
Problem Statement
In AtCoder Kingdom, Gregorian calendar is used, and dates are written in the "year-month-day" order, or the "month-day" order without the year.
For example, May
3
,
2018
is written as
2018
-
5
-
3
, or
5
-
3
without the year.
In this country, a date is called
Takahashi
when the month and the day are equal as numbers. For example,
5
-
5
is Takahashi.
How many days from
2018
-
1
-
1
through
2018
-
a
-
b
are Takahashi?
Constraints
a
is an integer between
1
and
12
(inclusive).
b
is an integer between
1
and
31
(inclusive).
2018
-
a
-
b
is a valid date in Gregorian calendar.
Input
Input is given from Standard Input in the following format:
a
b
Output
Print the number of days from
2018
-
1
-
1
through
2018
-
a
-
b
that are Takahashi.
Sample Input 1
5 5
Sample Output 1
5
There are five days that are Takahashi:
1
-
1
,
2
-
2
,
3
-
3
,
4
-
4
and
5
-
5
.
Sample Input 2
2 1
Sample Output 2
1
There is only one day that is Takahashi:
1
-
1
.
Sample Input 3
11 30
Sample Output 3
11
There are eleven days that are Takahashi:
1
-
1
,
2
-
2
,
3
-
3
,
4
-
4
,
5
-
5
,
6
-
6
,
7
-
7
,
8
-
8
,
9
-
9
,
10
-
10
and
11
-
11
.
Problem Description: Score : 700 points
Problem Statement
You are given sequences
A
and
B
consisting of non-negative integers.
The lengths of both
A
and
B
are
N
, and the sums of the elements in
A
and
B
are equal.
The
i
-th element in
A
is
A_i
, and the
i
-th element in
B
is
B_i
.
Tozan and Gezan repeats the following sequence of operations:
If
A
and
B
are equal sequences, terminate the process.
Otherwise, first Tozan chooses a positive element in
A
and decrease it by
1
.
Then, Gezan chooses a positive element in
B
and decrease it by
1
.
Then, give one candy to Takahashi, their pet.
Tozan wants the number of candies given to Takahashi until the process is terminated to be as large as possible, while Gezan wants it to be as small as possible.
Find the number of candies given to Takahashi when both of them perform the operations optimally.
Constraints
1 \leq N \leq 2 × 10^5
0 \leq A_i,B_i \leq 10^9(1\leq i\leq N)
The sums of the elements in
A
and
B
are equal.
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_1
B_1
:
A_N
B_N
Output
Print the number of candies given to Takahashi when both Tozan and Gezan perform the operations optimally.
Sample Input 1
2
1 2
3 2
Sample Output 1
2
When both Tozan and Gezan perform the operations optimally, the process will proceed as follows:
Tozan decreases
A_1
by
1
.
Gezan decreases
B_1
by
1
.
One candy is given to Takahashi.
Tozan decreases
A_2
by
1
.
Gezan decreases
B_1
by
1
.
One candy is given to Takahashi.
As
A
and
B
are equal, the process is terminated.
Sample Input 2
3
8 3
0 1
4 8
Sample Output 2
9
Sample Input 3
1
1 1
Sample Output 3
0
Problem Description: Score : 700 points
Problem Statement
Aoki is playing with a sequence of numbers
a_{1}, a_{2}, ..., a_{N}
. Every second, he performs the following operation :
Choose a positive integer
k
. For each element of the sequence
v
, Aoki may choose to replace
v
with its remainder when divided by
k
, or do nothing with
v
. The cost of this operation is
2^{k}
(regardless of how many elements he changes).
Aoki wants to turn the sequence into
b_{1}, b_{2}, ..., b_{N}
(the order of the elements is important). Determine if it is possible for Aoki to perform this task and if yes, find the minimum cost required.
Constraints
1 \leq N \leq 50
0 \leq a_{i}, b_{i} \leq 50
All values in the input are integers.
Input
Input is given from Standard Input in the following format:
N
a_{1}
a_{2}
...
a_{N}
b_{1}
b_{2}
...
b_{N}
Output
Print the minimum cost required to turn the original sequence into
b_{1}, b_{2}, ..., b_{N}
. If the task is impossible, output
-1
instead.
Sample Input 1
3
19 10 14
0 3 4
Sample Output 1
160
Here's a possible sequence of operations :
Choose
k = 7
. Replace
19
with
5
,
10
with
3
and do nothing to
14
. The sequence is now
5, 3, 14
.
Choose
k = 5
. Replace
5
with
0
, do nothing to
3
and replace
14
with
4
. The sequence is now
0, 3, 4
.
The total cost is
2^{7} + 2^{5} = 160
.
Sample Input 2
3
19 15 14
0 0 0
Sample Output 2
2
Aoki can just choose
k = 1
and turn everything into
0
. The cost is
2^{1} = 2
.
Sample Input 3
2
8 13
5 13
Sample Output 3
-1
The task is impossible because we can never turn
8
into
5
using the given operation.
Sample Input 4
4
2 0 1 8
2 0 1 8
Sample Output 4
0
Aoki doesn't need to do anything here. The cost is
0
.
Sample Input 5
1
50
13
Sample Output 5
137438953472
Beware of overflow issues.
Problem Description: Score : 400 points
Problem Statement
We have a grid with
H
rows and
W
columns. The square at the
i
-th row and the
j
-th column will be called Square
(i,j)
.
The integers from
1
through
H×W
are written throughout the grid, and the integer written in Square
(i,j)
is
A_{i,j}
.
You, a magical girl, can teleport a piece placed on Square
(i,j)
to Square
(x,y)
by consuming
|x-i|+|y-j|
magic points.
You now have to take
Q
practical tests of your ability as a magical girl.
The
i
-th test will be conducted as follows:
Initially, a piece is placed on the square where the integer
L_i
is written.
Let
x
be the integer written in the square occupied by the piece. Repeatedly move the piece to the square where the integer
x+D
is written, as long as
x
is not
R_i
. The test ends when
x=R_i
.
Here, it is guaranteed that
R_i-L_i
is a multiple of
D
.
For each test, find the sum of magic points consumed during that test.
Constraints
1 \leq H,W \leq 300
1 \leq D \leq H×W
1 \leq A_{i,j} \leq H×W
A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))
1 \leq Q \leq 10^5
1 \leq L_i \leq R_i \leq H×W
(R_i-L_i)
is a multiple of
D
.
Input
Input is given from Standard Input in the following format:
H
W
D
A_{1,1}
A_{1,2}
...
A_{1,W}
:
A_{H,1}
A_{H,2}
...
A_{H,W}
Q
L_1
R_1
:
L_Q
R_Q
Output
For each test, print the sum of magic points consumed during that test.
Output should be in the order the tests are conducted.
Sample Input 1
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8
Sample Output 1
5
4
is written in Square
(1,2)
.
6
is written in Square
(3,3)
.
8
is written in Square
(3,1)
.
Thus, the sum of magic points consumed during the first test is
(|3-1|+|3-2|)+(|3-3|+|1-3|)=5
.
Sample Input 2
4 2 3
3 7
1 4
5 2
6 8
2
2 2
2 2
Sample Output 2
0
0
Note that there may be a test where the piece is not moved at all, and there may be multiple identical tests.
Sample Input 3
5 5 4
13 25 7 15 17
16 22 20 2 9
14 11 12 1 19
10 6 23 8 18
3 21 5 24 4
3
13 13
2 10
13 13
Sample Output 3
0
5
0
Problem Description: Score : 500 points
Problem Statement
An adult game master and
N
children are playing a game on an ice rink.
The game consists of
K
rounds.
In the
i
-th round, the game master announces:
Form groups consisting of
A_i
children each!
Then the children who are still in the game form as many groups of
A_i
children as possible.
One child may belong to at most one group.
Those who are left without a group leave the game. The others proceed to the next round.
Note that it's possible that nobody leaves the game in some round.
In the end, after the
K
-th round, there are exactly two children left, and they are declared the winners.
You have heard the values of
A_1
,
A_2
, ...,
A_K
. You don't know
N
, but you want to estimate it.
Find the smallest and the largest possible number of children in the game before the start, or determine that no valid values of
N
exist.
Constraints
1 \leq K \leq 10^5
2 \leq A_i \leq 10^9
All input values are integers.
Input
Input is given from Standard Input in the following format:
K
A_1
A_2
...
A_K
Output
Print two integers representing the smallest and the largest possible value of
N
, respectively,
or a single integer
-1
if the described situation is impossible.
Sample Input 1
4
3 4 3 2
Sample Output 1
6 8
For example, if the game starts with
6
children, then it proceeds as follows:
In the first round,
6
children form
2
groups of
3
children, and nobody leaves the game.
In the second round,
6
children form
1
group of
4
children, and
2
children leave the game.
In the third round,
4
children form
1
group of
3
children, and
1
child leaves the game.
In the fourth round,
3
children form
1
group of
2
children, and
1
child leaves the game.
The last
2
children are declared the winners.
Sample Input 2
5
3 4 100 3 2
Sample Output 2
-1
This situation is impossible.
In particular, if the game starts with less than
100
children, everyone leaves after the third round.
Sample Input 3
10
2 2 2 2 2 2 2 2 2 2
Sample Output 3
2 3
Problem Description: Score : 200 points
Problem Statement
Find the largest square number not exceeding
N
. Here, a
square number
is an integer that can be represented as the square of an integer.
Constraints
1 \leq N \leq 10^9
N
is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print the largest square number not exceeding
N
.
Sample Input 1
10
Sample Output 1
9
10
is not square, but
9 = 3 × 3
is. Thus, we print
9
.
Sample Input 2
81
Sample Output 2
81
Sample Input 3
271828182
Sample Output 3
271821169
Problem Description: Score : 400 points
Problem Statement
There are
N
squares in a row.
The leftmost square contains the integer
A
, and the rightmost contains the integer
B
. The other squares are empty.
Aohashi would like to fill the empty squares with integers so that the following condition is satisfied:
For any two adjacent squares, the (absolute) difference of the two integers in those squares is between
C
and
D
(inclusive).
As long as the condition is satisfied, it is allowed to use arbitrarily large or small integers to fill the squares.
Determine whether it is possible to fill the squares under the condition.
Constraints
3 \leq N \leq 500000
0 \leq A \leq 10^9
0 \leq B \leq 10^9
0 \leq C \leq D \leq 10^9
All input values are integers.
Input
Input is given from Standard Input in the following format:
N
A
B
C
D
Output
Print
YES
if it is possible to fill the squares under the condition; print
NO
otherwise.
Sample Input 1
5 1 5 2 4
Sample Output 1
YES
For example, fill the squares with the following integers:
1
,
-1
,
3
,
7
,
5
, from left to right.
Sample Input 2
4 7 6 4 5
Sample Output 2
NO
Sample Input 3
48792 105960835 681218449 90629745 90632170
Sample Output 3
NO
Sample Input 4
491995 412925347 825318103 59999126 59999339
Sample Output 4
YES
Problem Description: Score : 1000 points
Problem Statement
There are
N
barbecue restaurants along a street.
The restaurants are numbered
1
through
N
from west to east, and the distance between restaurant
i
and restaurant
i+1
is
A_i
.
Joisino has
M
tickets, numbered
1
through
M
.
Every barbecue restaurant offers barbecue meals in exchange for these tickets.
Restaurant
i
offers a meal of
deliciousness
B_{i,j}
in exchange for ticket
j
.
Each ticket can only be used once, but any number of tickets can be used at a restaurant.
Joisino wants to have
M
barbecue meals by starting from a restaurant of her choice, then repeatedly traveling to another barbecue restaurant and using unused tickets at the restaurant at her current location.
Her eventual
happiness
is calculated by the following formula: "(The total deliciousness of the meals eaten) - (The total distance traveled)".
Find her maximum possible eventual happiness.
Constraints
All input values are integers.
2≤N≤5×10^3
1≤M≤200
1≤A_i≤10^9
1≤B_{i,j}≤10^9
Input
The input is given from Standard Input in the following format:
N
M
A_1
A_2
...
A_{N-1}
B_{1,1}
B_{1,2}
...
B_{1,M}
B_{2,1}
B_{2,2}
...
B_{2,M}
:
B_{N,1}
B_{N,2}
...
B_{N,M}
Output
Print Joisino's maximum possible eventual happiness.
Sample Input 1
3 4
1 4
2 2 5 1
1 3 3 2
2 2 5 1
Sample Output 1
11
The eventual happiness can be maximized by the following strategy: start from restaurant
1
and use tickets
1
and
3
, then move to restaurant
2
and use tickets
2
and
4
.
Sample Input 2
5 3
1 2 3 4
10 1 1
1 1 1
1 10 1
1 1 1
1 1 10
Sample Output 2
20