Problem Statement

Takahashi works as a floor staff member at a restaurant. Today, he received exactly one dish order from each of N customers.

The dish that the i-th (1 \leq i \leq N) customer actually ordered is T_i, but the dish name that Takahashi relayed to the kitchen was S_i. Since there may have been mishearings or miscommunications, Takahashi decided to verify the orders.

Find the number of customers for whom the actual order T_i and the relayed order S_i differ, that is, the number of customers whose orders were incorrectly communicated.

Constraints

• 1 \leq N \leq 10^5
• N is an integer.
• T_i and S_i are strings of lowercase English letters with length between 1 and 20, inclusive.

Sample Input 1

4
ramen ramen
sushi susi
curry curry
pasta pizza

Sample Output 1

2

Sample Input 2

3
tea tea
cake cake
salad salad

Sample Output 2

0

Sample Input 3

10
ramen ramen
sushi sushi
pizza piza
burger burger
salad salad
omelet omelette
steak steak
pasta pasta
soup soap
juice juice

Sample Output 3

3

Sample Input 4

20
ramen ramen
sushi sushi
curry curry
pasta pasta
salad salsa
burger buger
steak steak
soup soup
juice joice
coffee coffee
tea tea
cake cake
icecream icecream
sandwich sandwitch
dumpling dumpling
noodle noodel
omelet omelet
pancake pancake
chicken chicken
fish dish

Sample Output 4

6

Sample Input 5

1
aaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbb

Sample Output 5

1

Problem Statement

Takahashi is playing an RPG game. On a game stage, N monsters are lined up in a row, numbered 1, 2, \ldots, N from left to right. Monster i has strength D_i, and defeating it yields a reward of V_i gold.

Takahashi starts with attack power 0 and 0 gold. When Takahashi defeats a monster, he absorbs that monster's power, increasing his attack power. Below, we denote Takahashi's current attack power as h.

Takahashi visits the monsters in order from the left: monster 1, 2, \ldots, N, visiting each monster exactly once.

Additionally, Takahashi has an empty stack called the "postpone stack" (LIFO: a data structure where the last element added is the first to be removed). The element that was added to the stack last (the next element to be removed) is called the "top element."

When Takahashi visits monster i, he follows these rules:

• If D_i > h, his attack power is insufficient, so he postpones that monster. The postponed monster is added to the top of the postpone stack. In this case, the postpone resolution process is not performed.
• If D_i \leq h, he defeats that monster. Upon defeating it, he receives a reward of V_i gold, and his attack power increases by that monster's strength (h \leftarrow h + D_i). Immediately after defeating the monster, the following "postpone resolution process" is performed.

Postpone resolution process: Repeat the following operations until the termination condition is met.

1. If the postpone stack is empty, terminate the process.
2. Check the strength of the monster on top of the stack.

• If that strength is h or less, remove that monster from the stack and defeat it. Upon defeating it, receive the reward and increase attack power by that monster's strength, just as usual. Then, return to step 1.
• If that strength is greater than h, terminate the process.

Note: In the postpone resolution process, only the top of the stack is ever checked. When the top monster is defeated and removed, the monster that was below it becomes the new top and is the next to be checked. Elements in the middle of the stack are never skipped over and checked.

After visiting all monsters 1, 2, \ldots, N in order and performing the above rules for each, one final "postpone resolution process" is performed.

After this entire sequence of operations is complete, if any monsters remain in the postpone stack, they are treated as undefeated. No reward is obtained from undefeated monsters, and no attack power increase occurs.

Determine the total gold Takahashi receives as reward.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq D_i \leq 10^9
• 1 \leq V_i \leq 10^9
• All input values are integers.

Sample Input 1

5
0 10
3 20
1 15
0 5
2 30

Sample Output 1

15

Sample Input 2

4
5 100
3 50
2 30
1 10

Sample Output 2

0

Sample Input 3

8
0 10
0 5
3 20
1 15
2 30
10 100
5 50
4 25

Sample Output 3

15

Sample Input 4

12
0 100
0 50
1 200
3 150
2 80
0 10
5 300
4 120
10 500
8 250
6 180
20 1000

Sample Output 4

160

Sample Input 5

1
0 1000000000

Sample Output 5

1000000000

Problem Statement

There are N people, numbered from 1 to N. There are a total of M one-way communication channels among the people. The i-th communication channel allows person U_i to send a message to person V_i.

Initially (at the start of day 0), only person S knows a certain rumor. The spread of the rumor proceeds day by day according to the following rules:

• Each person who knows the rumor at the start of day d (d = 0, 1, 2, \ldots) simultaneously sends the rumor through all communication channels originating from that person. The sent rumors arrive at the start of day d+1, and the recipients become aware of the rumor from that point onward.
• A person who newly learns the rumor at the start of day d+1 can only actually send the rumor from day d+1 onward.
• Once a person learns the rumor, they remain aware of it permanently.

Find the day d when all people first become aware of the rumor. That is, output the smallest d such that at the start of day d, all people know the rumor for the first time. If all people already know the rumor at the start of day 0 (such as when N = 1), output 0. If the rumor cannot reach all people no matter how many days pass, output -1.

Constraints

• 1 \leq N \leq 4 \times 10^5
• 0 \leq M < 2 \times 10^5
• 1 \leq S \leq N
• 1 \leq U_i \leq N
• 1 \leq V_i \leq N
• U_i \neq V_i (no self-loops exist)
• Each ordered pair (U_i, V_i) appears at most once
• All input values are integers

Sample Input 1

4 4 1
1 2
1 3
2 4
3 4

Sample Output 1

2

Sample Input 2

5 4 2
2 3
3 4
4 2
1 5

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

4

Sample Input 4

15 22 10
10 1
10 2
10 3
1 4
1 5
2 5
2 6
3 6
3 7
4 8
5 8
5 9
6 9
6 11
7 11
8 12
8 9
9 13
11 14
12 15
13 15
14 15

Sample Output 4

5

Sample Input 5

1 0 1

Sample Output 5

0

Problem Statement

Takahashi has N books arranged in a row from left to right on his bookshelf. The i-th book from the left has A_i pages, and to remove this book from the bookshelf and have it taken by a used bookstore, Takahashi must pay a handling fee of C_i. No fee is charged for books that remain on the bookshelf.

To improve the appearance of his bookshelf, Takahashi wants to remove some books so that the page counts of the remaining books are strictly monotonically increasing from left to right. That is, when looking at the remaining books from left to right, for any two adjacent books, the page count of the left book must be strictly less than the page count of the right book. Note that since books are only removed and not rearranged, the relative order of the remaining books is the same as the original order.

The number of books removed may be any number from 0 to N, inclusive. The strictly monotonically increasing condition is considered satisfied when 0 or 1 books remain.

Find the minimum total handling fee of the removed books when choosing which books to remove so that the page counts of the remaining books are strictly monotonically increasing from left to right.

Constraints

• 1 \leq N \leq 5000
• 1 \leq A_i \leq 10^9
• 1 \leq C_i \leq 10^9
• All input values are integers.

Sample Input 1

5
3 1 4 1 5
10 20 30 40 50

Sample Output 1

50

Sample Input 2

4
5 5 5 5
3 1 4 2

Sample Output 2

6

Sample Input 3

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

Sample Output 3

31

Sample Input 4

20
15 8 23 42 11 37 5 29 44 18 3 50 33 21 46 9 38 27 41 12
7 12 3 9 15 6 20 4 11 8 18 2 14 10 5 16 1 13 7 19

Sample Output 4

135

Sample Input 5

1
1000000000
1000000000

Sample Output 5

0

Problem Statement

2^N students are standing in a row from left to right, and each student is wearing either a red hat or a white hat. The hat colors of the students are represented by a string S of length 2^N. For the i-th student from the left, if the i-th character of S is 0, they are wearing a red hat, and if it is 1, they are wearing a white hat.

Takahashi, in preparation for the sports festival, can perform the following operation at most once:

• Choose an integer l (1 \leq l \leq 2^N - K + 1), and rearrange the K consecutive students from the l-th to the (l+K-1)-th from the left. As a result of the rearrangement, all students with red hats within the interval are placed consecutively on the left side of the interval, and all students with white hats are placed consecutively on the right side of the interval. The positions of students outside the interval do not change.

After the operation (or as-is if no operation is performed), the students are recursively divided into groups according to the following rules:

1. Initially, all students from the 1-st to the 2^N-th from the left form one group.
2. A group with 2 or more people is split into two groups: one consisting of the first half of students (counted from the left) and one consisting of the second half.
3. This splitting is repeated until each group contains exactly 1 person.

Consider all groups that appear during this process (including the initial whole group, groups at each intermediate stage, and the final single-person groups — a total of 2^{N+1} - 1 groups). A group is called a "balanced group" if the number of students with red hats and the number of students with white hats within the group are equal. Note that a single-person group cannot satisfy this condition, so it is never a balanced group.

Find the maximum possible number of balanced groups when Takahashi optimally chooses whether to perform the operation and the position of the interval.

Constraints

• 1 \leq N
• 2^N \leq 10^6
• 1 \leq K \leq 2^N
• S is a string of length 2^N consisting of 0 and 1
• N, K are integers

Sample Input 1

2 2
0110

Sample Output 1

3

Sample Input 2

3 3
01011001

Sample Output 2

7

Sample Input 3

5 7
00110101111000010100111011001010

Sample Output 3

19

Sample Input 4

8 64
0100110010110001111001011010100011110000101010100101001111001100000111010010110111001000101101111010101000001111111100000101010101100110011010010101101011000011100100111011010001001011011110000011001111001100001111000011110011001010010101100011101010010111

Sample Output 4

146

Sample Input 5

1 1
01

Sample Output 5

1