Problem Statement

Takahashi is trying to enter his PIN at a bank ATM. On this ATM, the PIN is entered using two types of buttons: L (left button) and R (right button).

Takahashi thought he remembered the correct PIN, but due to nervousness, he might have made mistakes several times. The ATM screen displays in real-time whether each entered digit is correct or not.

Takahashi will now enter an N-digit PIN one digit at a time. Given the correct PIN and the sequence of buttons that Takahashi actually pressed, find the maximum number of consecutive digits that Takahashi entered correctly.

Here, "the number of consecutive correctly entered digits" refers to the number of consecutive times he pressed the correct button without making a mistake.

Constraints

• 1 \leq N \leq 2 \times 10^5
• S is a string of length N
• T is a string of length N
• Each character of S is L or R
• Each character of T is L or R

Sample Input 1

5
LLRRL
LLRLL

Sample Output 1

3

Sample Input 2

4
LLLL
RRRR

Sample Output 2

0

Sample Input 3

10
LRLRLRLRLR
LRLRLLRLRR

Sample Output 3

5

Sample Input 4

20
RLRLRLRLRLRLRLRLRLRL
RLRLRLRLRLRLRLRLRLRL

Sample Output 4

20

Sample Input 5

1
L
R

Sample Output 5

0

Problem Statement

Takahashi is a farm manager. Takahashi's farm has N fields, each numbered from 1 to N.

Each field i has a required amount of work D_i needed for harvest. Initially, the cumulative work done on each field is 0. When the cumulative work on field i reaches D_i or more, the crops in that field become ready for harvest.

Takahashi's farm has M workers. Each worker can perform exactly 1 unit of work per day.

Every day, Takahashi must assign all M workers, each to exactly one field (multiple workers can be assigned to the same field). Workers cannot rest or be left unassigned to any field. If k workers are assigned to field i on a given day, the cumulative work on field i increases by k on that day. Workers can be assigned to fields that are already ready for harvest, but this only increases the cumulative work on that field and has no effect on the harvest.

The assignment of workers can be decided independently each day.

Determine the minimum number of days required for all fields to become ready for harvest when Takahashi assigns workers optimally.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq M \leq 10^9
• 1 \leq D_i \leq 10^9
• All input values are integers

Sample Input 1

3 2
1 2 3

Sample Output 1

3

Sample Input 2

4 5
2 1 4 3

Sample Output 2

2

Sample Input 3

10 7
5 12 8 20 3 15 7 11 9 15

Sample Output 3

15

Sample Input 4

30 13
41 27 63 18 52 36 75 29 44 58 31 69 22 47 55 38 61 24 73 19 46 57 33 66 28 49 54 37 62 21

Sample Output 4

103

Sample Input 5

1 1000000000
1000000000

Sample Output 5

1

Problem Statement

Takahashi manages a network consisting of N computers 1, 2, \ldots, N and N cables. The i-th cable (1 \leq i \leq N) connects computer A_i and computer B_i bidirectionally. There may exist cables connecting a computer to itself (self-loops, i.e., A_i = B_i), as well as multiple cables connecting the same pair of computers (multi-edges).

Takahashi can choose and remove at most K distinct cables from the N cables.

Determine whether it is possible to make the network cycle-free (i.e., a forest) by appropriately choosing and removing cables.

Here, a network contains a cycle means that there exists a path starting from some computer v, traversing one or more cables, and returning to v, without passing through the same cable twice. In particular, a self-loop forms a cycle by itself, and multi-edges (two or more cables connecting the same pair of computers) also contain a cycle.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq K \leq N
• 1 \leq A_i, B_i \leq N
• All inputs are integers.

Sample Input 1

4 1
1 2
2 3
3 1
3 4

Sample Output 1

Yes

Sample Input 2

4 0
1 2
2 3
3 1
3 4

Sample Output 2

No

Sample Input 3

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

Sample Output 3

Yes

Sample Input 4

25 5
1 2
2 3
3 4
4 1
4 5
5 6
7 8
7 8
8 9
9 10
10 11
12 12
12 13
13 14
14 15
15 16
17 18
18 19
19 20
20 17
21 22
22 23
23 21
23 24
24 25

Sample Output 4

Yes

Sample Input 5

1 1
1 1

Sample Output 5

Yes

Problem Statement

There is a town consisting of N intersections and M bidirectional roads. The intersections are numbered 1 to N.

Takahashi wants to guide a lost kitten, currently at intersection N, to his home at intersection 1. Since the kitten is shy and cannot be carried directly, Takahashi decides to place signposts (glowing markers) at some intersections to guide the kitten to his home.

At most one signpost can be placed at each intersection. Takahashi decides all the intersections to place signposts before the kitten starts moving. He cannot add, remove, or move signposts while the kitten is moving.

Each signpost has two states: "active" and "inactive (fallen)". All placed signposts are initially in the "active" state. Once a signpost falls, it never becomes active again.

Meanwhile, Aoki wants to obstruct Takahashi. Aoki has placed barricades at K intersections, and Takahashi cannot place a signpost at any intersection with a barricade. However, no barricades are placed at intersection 1 and intersection N. Takahashi can place a signpost at any intersection without a barricade (including intersection 1 and intersection N).

Kitten's Movement Rules

The kitten starts from intersection N and repeats the following steps:

1. Arrival Check: If the kitten is at intersection 1, the guidance is successful, and the movement ends immediately.
2. Determining the Destination: The kitten checks if there are any intersections directly connected (adjacent) to its current intersection by a road that have an active signpost.

• If there is at least one such adjacent intersection, the kitten moves to the one with the smallest intersection number.
• If there are no such adjacent intersections, the kitten cannot move further, and the movement ends (guidance fails).

1. State Change of Signposts: If a signpost is placed at the intersection the kitten has just moved to, and that intersection is not intersection 1, the signpost falls and becomes inactive immediately upon arrival. A signpost placed at intersection 1 never falls. After this, return to Step 1.

Notes:

• The kitten's starting point is intersection N. At the start, the kitten has not "moved from" anywhere, so even if a signpost is placed at intersection N, it does not fall and remains active.
• Since the signpost at intersection 1 does not fall, it functions as a marker to guide the kitten to intersection 1 from adjacent intersections. However, once the kitten arrives at intersection 1, the guidance succeeds, so it does not affect any subsequent movement.
• Since signposts at intersections other than intersection 1 fall upon arrival, the kitten will never be guided to the same intersection (excluding intersection 1) more than once. Therefore, the kitten's movement is guaranteed to end in a finite number of steps.

Find the minimum number of signposts required to guide the kitten from intersection N to intersection 1. If it is impossible to guide the kitten to intersection 1 no matter how the signposts are placed, output -1.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 0 \leq K \leq N - 2
• 1 \leq U_i, V_i \leq N
• U_i \neq V_i
• There is at most one road connecting the same pair of intersections.
• 1 \leq B_j \leq N (1 \leq j \leq K)
• B_j \neq 1 and B_j \neq N (1 \leq j \leq K)
• B_1, B_2, \ldots, B_K are all distinct.
• All input values are integers.

Sample Input 1

4 3 0
4 3
3 2
2 1

Sample Output 1

3

Sample Input 2

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

Sample Output 2

-1

Sample Input 3

12 17 2
12 9
12 8
12 11
9 7
9 5
8 6
8 4
11 10
11 3
7 2
5 2
4 2
3 2
2 1
7 6
5 6
4 10
6 10

Sample Output 3

4

Sample Input 4

30 45 5
1 2
1 3
2 4
2 5
3 6
3 7
4 8
5 8
5 9
6 10
6 11
7 11
8 12
9 13
10 14
11 15
12 16
12 18
13 17
14 18
15 19
16 20
17 21
18 24
19 23
20 24
21 25
22 26
23 27
24 30
25 29
26 30
27 30
28 29
29 30
4 14
7 17
9 22
10 20
11 21
13 23
16 26
18 28
19 29
2 12
14 17 22 25 28

Sample Output 4

5

Sample Input 5

2 1 0
1 2

Sample Output 5

1

Problem Statement

Takahashi is trying to make N types of dishes.

The dishes are numbered from 1 to N, and completing dish i gives him a satisfaction of A_i (satisfaction can be negative).

Each dish has 0 or more "failure conditions" set for it. Multiple failure conditions may be set for the same dish.

A failure condition is represented by a pair (p, S) of a target dish p and a set of dishes S (not containing p), with the following meaning:

• If, at the time dish p is started, all dishes in set S have already been completed, then dish p meets this failure condition and cannot be completed.

In particular, if S is the empty set, the failure condition is unconditionally met, so dish p can never be completed.

Takahashi selects any number of dishes he likes from the N types (he may select none), and makes them one by one in any order he likes. Each dish can be made at most once. However, if at the time he starts making a dish, even one of the failure conditions for that dish is met, the dish cannot be completed. Takahashi plans ahead and chooses to make only dishes that will certainly be completed, in order.

Formally, Takahashi selects a sequence of distinct dishes a_1, a_2, \dots, a_k (0 \leq k \leq N). This sequence is feasible if, for all t = 1, 2, \dots, k, every failure condition (a_t, S) related to dish a_t satisfies

S \nsubseteq \{ a_1, a_2, \dots, a_{t-1} \}

Here, \{a_1, \dots, a_{t-1}\} is the set of dishes completed before dish a_t, and when t = 1, it is the empty set (dish a_t itself is not included in this set).

When a feasible sequence is chosen, the total satisfaction obtained is

A_{a_1} + A_{a_2} + \cdots + A_{a_k}

(When k = 0, the satisfaction is 0.)

Find the maximum total satisfaction over all feasible sequences.

Constraints

• 1 \leq N \leq 19
• 0 \leq M \leq 10^5
• -10^9 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq p_q \leq N (1 \leq q \leq M)
• 0 \leq c_q \leq N - 1 (1 \leq q \leq M)
• 1 \leq x_{q,j} \leq N (1 \leq q \leq M,\ 1 \leq j \leq c_q)
• x_{q,j} \neq p_q (1 \leq q \leq M,\ 1 \leq j \leq c_q)
• Within the same failure condition, x_{q,1}, x_{q,2}, \dots, x_{q,c_q} are all distinct
• \displaystyle \sum_{q=1}^{M} c_q \leq 2 \times 10^5
• All input values are integers

Sample Input 1

3 2
5 10 -3
2 1 1
3 0

Sample Output 1

15

Sample Input 2

4 3
-5 7 4 6
4 2 2 3
2 1 1
3 1 1

Sample Output 2

17

Sample Input 3

8 10
8 -4 15 6 -10 12 3 9
3 1 1
4 2 2 3
6 0
7 3 1 4 5
8 2 3 6
1 1 8
5 2 2 7
2 1 5
4 1 7
8 3 1 2 4

Sample Output 3

41

Sample Input 4

15 25
20 -7 35 14 -12 8 50 -30 22 5 -3 18 40 -25 11
7 2 1 3
3 1 7
13 3 2 4 6
5 0
8 1 9
9 2 10 11
12 4 1 5 7 9
15 2 13 14
2 1 15
4 3 2 8 12
10 2 6 7
11 1 10
6 5 1 2 3 4 5
14 2 7 13
1 4 4 8 12 15
13 1 7
7 3 5 9 11
9 0
15 5 1 3 5 7 9
12 2 10 14
4 1 1
6 2 8 11
2 3 3 4 5
10 4 1 9 13 15
11 2 6 12

Sample Output 4

201

Sample Input 5

1 1
1000000000
1 0

Sample Output 5

0