Problem Statement

Takahashi is a security guard who manages N checkpoints arranged in a straight line.

The checkpoints are numbered 1, 2, \ldots, N from left to right, and it takes exactly 1 second to move between adjacent checkpoints. Takahashi's station is at checkpoint N.

When an anomaly detection alarm sounds, Takahashi departs from his station (checkpoint N) and travels through the checkpoints in the order N, N-1, \ldots, 1 until he reaches checkpoint 1. He then turns around and travels through the checkpoints in the order 1, 2, \ldots, N, returning to his station (checkpoint N). The time required for inspection at each checkpoint and for turning around is 0 seconds. Therefore, the travel time for one patrol is 2(N-1) seconds.

Takahashi always returns to his station before departing for the next patrol. All M patrols follow the same route and take the same travel time.

One day, the alarm sounded M times, and Takahashi performed M round-trip patrols. Find the total travel time (in seconds) for Takahashi's M patrols that day. Note that waiting time between patrols is not included.

Constraints

• 1 \leq N \leq 10^9
• 1 \leq M \leq 10^9
• All inputs are integers

Sample Input 1

3 1

Sample Output 1

4

Sample Input 2

5 4

Sample Output 2

32

Sample Input 3

1000000000 1000000000

Sample Output 3

1999999998000000000

Problem Statement

Takahashi is organizing an event spanning N days at his school's cultural festival. The venue has M classrooms, and each classroom is scheduled to hold exactly one lecture per day. Classroom j (1 \leq j \leq M) has a capacity of C_j people.

On day i (1 \leq i \leq N), K_i visitors come to the cultural festival. Each visitor specifies exactly one classroom they wish to attend. Let P_{i,k} denote the classroom number desired by the k-th visitor (1 \leq k \leq K_i) on day i. Note that multiple visitors may wish to attend the same classroom on the same day.

For each day, the following process is performed (the processing for each day is independent, and the result of one day does not affect another day). The number of applicants for each classroom on that day is tallied. If the number of applicants for a classroom is at most its capacity (i.e., number of applicants \leq capacity), then all applicants can attend that classroom's lecture. On the other hand, if the number of applicants exceeds the capacity (i.e., number of applicants > capacity), the lecture in that classroom is canceled for safety reasons, and none of the visitors who wished to attend that classroom can participate in any lecture. Furthermore, visitors whose desired classroom's lecture was canceled are not reassigned to other classrooms.

Determine the total number of visitors who actually attended a lecture across all N days of the event (the sum of the number of participants in each classroom on each day).

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq C_j \leq 10^9 (1 \leq j \leq M)
• 1 \leq K_i (1 \leq i \leq N)
• \displaystyle \sum_{i=1}^{N} K_i \leq 2 \times 10^5
• 1 \leq P_{i,k} \leq M (1 \leq i \leq N,\ 1 \leq k \leq K_i)
• All input values are integers.

Sample Input 1

2 3
3 2 4
5
1 2 1 2 2
3
1 3 3

Sample Output 1

5

Sample Input 2

3 4
2 5 1 3
6
1 2 1 4 1 2
4
2 2 2 2
5
1 3 4 3 4

Sample Output 2

10

Sample Input 3

4 5
3 1 4 2 5
8
1 2 1 3 5 2 1 5
6
3 1 3 3 3 3
7
2 4 5 4 5 5 5
3
4 1 4

Sample Output 3

17

Problem Statement

Takahashi is developing a text editor. This editor has a feature that performs bulk character replacement across multiple text files.

One day, Takahashi opened N text files. Each file contains a single line consisting of a string of lowercase English letters.

Takahashi will perform Q replacement operations on these files in order. In each operation, a specific character contained in all current files is replaced with another character all at once.

After all replacement operations are completed, output the string written in each file.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq |S_i| \leq 10^5
• \sum_{i=1}^{N} |S_i| \leq 10^6
• S_i consists only of lowercase English letters
• a_j, b_j are lowercase English letters

Sample Input 1

3 2
abc
dog
banana
a b
b c

Sample Output 1

ccc
dog
ccncnc

Sample Input 2

2 3
hello
world
l x
o a
x l

Sample Output 2

hella
warld

Sample Input 3

5 5
abcdefghij
programming
contest
algorithm
datastructure
a z
e a
z e
t s
s t

Sample Output 3

ebcdafghij
progremming
contatt
elgorithm
detettructura

Sample Input 4

10 8
thequickbrownfoxjumpsoverthelazydog
abcdefghijklmnopqrstuvwxyz
aabbccddee
zzzzzyyyyyxxxxx
helloworldfromcompetitiveprogramming
substitutioncipherexample
replacementoperation
queriesandfiles
multiplestrings
finaloutputtest
a b
b c
c d
d e
e f
f g
g h
z a

Sample Output 4

thhquihkhrownhoxjumpsovhrthhlhayhoh
hhhhhhhhijklmnopqrstuvwxya
hhhhhhhhhh
aaaaayyyyyxxxxx
hhlloworlhhromhomphtitivhprohrhmminh
suhstitutionhiphhrhxhmplh
rhplhhhmhntophrhtion
quhrihshnhhilhs
multiplhstrinhs
hinhloutputthst

Sample Input 5

1 1
a
a b

Sample Output 5

b

Problem Statement

Takahashi has come to a store with a budget of K yen.

The store has N items on display, and the price of the i-th item is C_i yen. Takahashi can choose any items he likes from these items to purchase, but he can buy at most one of each item. He may also choose to buy nothing at all.

However, the total price of the purchased items must not exceed the budget of K yen.

Takahashi wants to maximize the total price of the purchased items while satisfying this condition.

Among all ways to select items such that the total price is at most K, find the maximum possible total price.

Constraints

• 1 \leq N \leq 100
• 1 \leq K \leq 10^4
• 1 \leq C_i \leq 10^4 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

3 10
3 5 4

Sample Output 1

9

Sample Input 2

5 20
6 8 3 11 7

Sample Output 2

20

Sample Input 3

10 100
12 25 8 33 17 45 6 19 30 14

Sample Output 3

100

Problem Statement

Takahashi is trying to visit the summits of N mountains lined up in a row along a traverse route. The summits are numbered 1, 2, \ldots, N from the entrance side of the route, and Takahashi starts from the entrance and proceeds one-way from lower-numbered to higher-numbered summits. He cannot return to a summit he has already passed.

Each summit i has an "entrance fee" of C_i yen and an "elevation" of S_i. As Takahashi proceeds along the route, when he reaches each summit, he can choose either to climb it or to pass through without climbing. If he passes through without climbing, no entrance fee is charged. If he climbs it, he must pay that summit's entrance fee.

Takahashi has particular preferences for his mountaineering and wants to select which summits to climb such that all of the following conditions are satisfied:

• Upper limit on number of climbs: The number of summits climbed must be at most K.
• Strictly increasing elevation: When the climbed summits are listed in ascending order of their numbers, their elevations must be strictly increasing. That is, if he climbs summits i_1 < i_2 < \cdots < i_m in order, then S_{i_1} < S_{i_2} < \cdots < S_{i_m} must hold.
• Budget constraint: The total entrance fees of the climbed summits must not exceed his funds of B yen. That is, C_{i_1} + C_{i_2} + \cdots + C_{i_m} \leq B must hold.

Takahashi wants to maximize the number of summits climbed m while satisfying all the above conditions. Find the maximum value of m. Note that climbing no summits (m = 0) is also allowed.

Constraints

• 1 \leq N \leq 500
• 1 \leq K \leq 50
• 1 \leq B \leq 500
• 1 \leq C_i \leq B (1 \leq i \leq N)
• 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
• S_i \neq S_j (i \neq j)
• All inputs are integers.

Sample Input 1

5 3 10
3 100
2 200
5 150
4 300
1 400

Sample Output 1

3

Sample Input 2

4 3 3
2 100
2 200
2 300
2 400

Sample Output 2

1

Sample Input 3

10 5 20
3 500
2 100
5 300
1 200
4 800
2 600
3 150
6 900
1 700
5 1000

Sample Output 3

5

Sample Input 4

20 10 50
5 320
3 150
7 410
2 80
4 500
6 230
1 600
8 90
3 700
5 350
2 850
4 120
6 950
1 40
3 1100
7 560
2 1200
5 780
4 1350
3 999

Sample Output 4

10

Sample Input 5

1 1 1
1 1000000000

Sample Output 5

1