Problem Statement

Takahashi is the leader of a music club. There are N members in the club, excluding Takahashi.

To decide which songs to perform at the next club activity, Takahashi prepared a candidate list of M songs numbered from 1 to M. Each of the N members selected one or more songs they want to perform from this list (without selecting the same song more than once) and reported their choices to Takahashi. Note that Takahashi himself does not select any songs.

The i-th member (1 \leq i \leq N) selected K_i songs, and the numbers of the selected songs were C_{i,1}, C_{i,2}, \ldots, C_{i,K_i}.

Find the number of songs that were selected by all N members in common. In other words, among the songs numbered from 1 to M, output how many songs were selected by all N members.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq K_i \leq M
• 1 \leq C_{i,1} < C_{i,2} < \cdots < C_{i,K_i} \leq M (The song numbers selected by each member are distinct and given in strictly ascending order)
• \sum_{i=1}^{N} K_i \leq 2 \times 10^5
• All input values are integers

Sample Input 1

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

Sample Output 1

2

Sample Input 2

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

Sample Output 2

0

Sample Input 3

5 100
10 5 10 20 30 40 50 60 70 80 90
8 5 10 20 30 50 70 80 90
12 1 5 10 15 20 25 30 50 70 80 90 100
6 5 10 30 50 70 90
9 5 10 20 30 50 60 70 80 90

Sample Output 3

6

Problem Statement

Takahashi is going to attempt a mountain trail hiking course.

This hiking course has N checkpoints, numbered from checkpoint 1 to N. The course is a single path, and Takahashi starts at checkpoint 1 and proceeds in the order of checkpoints 1, 2, 3, \ldots, N. Takahashi can end the hike at any checkpoint he likes. That is, he may stop at an intermediate checkpoint without proceeding further, or he may go all the way to checkpoint N.

Each checkpoint i (1 \leq i \leq N) has a "scenery score" S_i assigned to it. When Takahashi reaches checkpoint i, he gains the scenery score S_i. On the other hand, moving from checkpoint i to checkpoint i+1 costs a stamina cost of C_i (1 \leq i \leq N-1).

Takahashi ends the hike at some checkpoint k (1 \leq k \leq N). At that point, Takahashi's "hiking satisfaction" is calculated by the following formula:

\left(\sum_{i=1}^{k} S_i\right) - \left(\sum_{i=1}^{k-1} C_i\right)

In other words, it is the total scenery scores gained from checkpoints 1 through k, minus the total stamina cost required to travel from checkpoint 1 to checkpoint k. When k = 1, no movement occurs, so the total stamina cost is 0, and the satisfaction is S_1.

Find the maximum value of "hiking satisfaction" when Takahashi optimally chooses the checkpoint at which to end the hike.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq C_i \leq 10^9 (1 \leq i \leq N-1)
• All inputs are integers.

Sample Input 1

5
5 3 8 2 6
4 10 1 3

Sample Output 1

6

Sample Input 2

4
10 1 1 1
100 100 100

Sample Output 2

10

Sample Input 3

12
7 15 3 20 6 8 25 4 10 12 5 18
5 12 4 30 2 7 20 1 15 3 9

Sample Output 3

25

Sample Input 4

20
13 8 21 5 34 2 18 27 6 11 40 3 16 9 25 7 30 4 14 22
6 20 4 10 30 1 15 35 2 8 12 25 5 18 3 28 7 9 11

Sample Output 4

66

Sample Input 5

1
1000000000

Sample Output 5

1000000000

Problem Statement

Takahashi visited an orchard where N fruit trees are lined up in a row. The trees are numbered 1, 2, \ldots, N from one end, and the i-th tree bears A_i fruits.

Takahashi walks past the trees one by one in order from tree 1 to tree N. He passes in front of each tree exactly once and cannot turn back. When passing in front of each tree, he chooses either to harvest all the fruits from that tree or to harvest none at all. He cannot harvest only a portion of the fruits. It is also allowed to harvest from no trees at all.

However, when he harvests fruits from a tree, the fatigue from harvesting prevents him from harvesting at the next K trees immediately after it. That is, if he harvests from the i-th tree, he cannot harvest from trees i+1 through i+K, and the earliest he can next harvest is from tree i+K+1 or later. In other words, if the trees he harvests from are listed in increasing order of their numbers, any two adjacent numbers i, j (i < j) in the list must satisfy j \geq i + K + 1. Note that when K = 0, this restriction allows harvesting from consecutive trees.

Find the maximum total number of fruits that Takahashi can harvest.

Constraints

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

Sample Input 1

5 2
3 7 2 5 8

Sample Output 1

15

Sample Input 2

8 1
10 20 30 40 50 60 70 80

Sample Output 2

200

Sample Input 3

15 3
100 50 30 20 200 10 5 150 80 40 300 25 15 60 250

Sample Output 3

850

Problem Statement

Takahashi lives in a city with N bus stops. The bus stops are numbered from 1 to N.

There are M bus routes operating in this city, numbered from 1 to M.

Bus route i passes through K_i bus stops A_{i,1}, A_{i,2}, \dots, A_{i,K_i}.

By taking this route, one can board at any one of these bus stops and get off at any other one of these bus stops.

Takahashi is initially at bus stop S and wants to go to bus stop T.

Takahashi can repeat the following operation any number of times (including zero):

• Choose a bus route that passes through the bus stop he is currently at and board it. Then get off at any bus stop (different from the current one) that the route passes through.

The same bus route may be used multiple times.

Find the minimum number of operations (i.e., the minimum number of rides) required to reach bus stop T. If it is impossible to reach it, output -1.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 10^5
• 1 \leq S \leq N
• 1 \leq T \leq N
• 1 \leq K_i \leq N （1 \leq i \leq M）
• 1 \leq A_{i,j} \leq N （1 \leq i \leq M,\ 1 \leq j \leq K_i）
• For each i, A_{i,1}, A_{i,2}, \dots, A_{i,K_i} are all distinct.
• \displaystyle \sum_{i=1}^{M} K_i \leq 5 \times 10^5
• All input values are integers.

Sample Input 1

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

Sample Output 1

2

Sample Input 2

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

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

3

Sample Input 4

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

Sample Output 4

3

Sample Input 5

1 1 1 1
1 1

Sample Output 5

0

Problem Statement

Takahashi is a curator at an art museum. The museum has N works as exhibition candidates, numbered from 1 to N. The evaluation score of the i-th work is H_i.

Takahashi has decided to select 1 or more works from these to exhibit. The same work cannot be selected more than once. The selected works are displayed in a row in ascending order of their numbers (the arrangement order cannot be freely changed).

To maintain a sense of unity in the exhibition, the sequence of arranged works must satisfy the following condition:

• Let k (k \geq 1) be the number of selected works, and let them be a_1, a_2, \ldots, a_k (a_1 < a_2 < \cdots < a_k) in ascending order of their numbers. Then, for all 1 \leq j \leq k-1, |H_{a_j} - H_{a_{j+1}}| \leq D must hold.

In other words, in the sequence of exhibited works arranged in order of their numbers, the absolute difference of evaluation scores between every two adjacent works must be at most D. When selecting only one work, there are no adjacent pairs, so this condition is automatically satisfied.

Takahashi wants to exhibit as many works as possible. Find the maximum number of works that can be selected while satisfying the above condition.

Constraints

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

Sample Input 1

5 3
4 1 5 8 3

Sample Output 1

3

Sample Input 2

5 0
3 1 3 3 2

Sample Output 2

3

Sample Input 3

10 5
10 3 8 12 7 15 9 6 11 2

Sample Output 3

7

Sample Input 4

20 10
50 45 55 40 35 30 25 20 28 33 38 43 48 53 58 63 68 60 55 50

Sample Output 4

19

Sample Input 5

1 0
1000000000

Sample Output 5

1