Problem Statement

Takahashi is analyzing the test results at his school.

There are N students in the class, assigned attendance numbers 1, 2, \ldots, N. The test score of the student with attendance number i is A_i points.

Takahashi decided to call students who scored at least K points (the passing threshold) "passers." The passers are divided into groups, and one award ceremony is held for each group.

The grouping is done according to the following rule. The set of attendance numbers of passers is partitioned into intervals of consecutive attendance numbers (maximal consecutive intervals that cannot be extended further by including additional passers at either end), and each interval forms one group. This partition is uniquely determined.

For example, when N = 10 and the attendance numbers of the passers are 2, 3, 4, 7, 9, 10, the groups are \{2, 3, 4\}, \{7\}, \{9, 10\}, resulting in 3 groups.

Find the number of groups. If there are no passers, the number of groups is 0.

Constraints

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

Sample Input 1

5 60
72 45 80 85 50

Sample Output 1

2

Sample Input 2

10 70
65 75 80 90 60 55 85 70 72 40

Sample Output 2

2

Sample Input 3

15 50
48 52 55 60 45 30 70 80 75 65 40 90 35 85 88

Sample Output 3

4

Problem Statement

Takahashi and Aoki are playing a card taking game against each other.

There are N cards laid out on the table. Each card is numbered from 1 to N, and card i has a positive integer A_i written on it.

The game proceeds according to the following rules:

1. Both players start with a score of 0.
2. Takahashi goes first, and Takahashi and Aoki take turns alternately.
3. On their turn, a player must choose exactly 1 card from the cards remaining on the table and take it (passing is not allowed). The taken card is removed from the table, and the integer written on that card is added to that player's score.
4. The game ends when all cards have been taken.

According to the above rules, Takahashi will take \lceil N/2 \rceil cards and Aoki will take \lfloor N/2 \rfloor cards.

Takahashi plays optimally to maximize (Takahashi's score) - (Aoki's score), and Aoki plays optimally to minimize (Takahashi's score) - (Aoki's score). Find (Takahashi's score) - (Aoki's score) when both players play optimally.

Constraints

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

Sample Input 1

3
10 20 30

Sample Output 1

20

Sample Input 2

5
1 2 3 4 5

Sample Output 2

3

Sample Input 3

8
100 50 80 120 90 30 70 60

Sample Output 3

60

Problem Statement

Takahashi has reached the last day of summer vacation. There are only M minutes remaining until summer vacation ends.

Takahashi has N homework assignments left. Each homework assignment i (1 \leq i \leq N) has a fixed evaluation score R_i received from the teacher upon completion, and a required time of T_i minutes to complete.

During these M minutes, Takahashi can choose some homework assignments to work on. However, the following conditions apply:

• Each homework assignment is either completed entirely or not attempted at all. It is not possible to partially complete an assignment. If he works on it, he must spend T_i minutes to complete it.
• He cannot work on the same homework assignment multiple times. That is, each homework assignment can be completed at most once.
• The total required time of the chosen homework assignments must be at most M minutes.

Under these conditions, Takahashi wants to maximize the total evaluation score of completed homework assignments.

Find the maximum total evaluation score that Takahashi can obtain.

Constraints

• 1 \leq N \leq 100
• 1 \leq M \leq 10^5
• 1 \leq R_i \leq 10^9
• 1 \leq T_i \leq M
• All inputs are integers

Sample Input 1

3 10
6 3
10 5
4 4

Sample Output 1

16

Sample Input 2

5 15
100 8
60 5
50 4
40 3
30 2

Sample Output 2

190

Sample Input 3

8 1000
1000000000 500
800000000 400
600000000 300
500000000 250
400000000 200
300000000 150
200000000 100
100000000 50

Sample Output 3

2000000000

Problem Statement

Takahashi is the president of a construction company in charge of developing an archipelago consisting of N remote islands. Each island is numbered from 1 to N.

Takahashi has been assigned a project to enable residents to travel between any pair of islands via bridges. Currently, there are M bridge construction proposals. The i-th proposal (1 \leq i \leq M) allows building a bridge that bidirectionally connects two distinct islands U_i and V_i. The cost to build this bridge is C_i ten-thousand yen. Note that there may be multiple proposals connecting the same pair of islands.

Takahashi wants to select some of these M proposals (each proposal can be selected at most once) to build bridges and make all islands connected. All islands being connected means that for any two islands, it is possible to travel from one to the other by traversing some sequence of built bridges. In particular, when N = 1, the islands are connected without building any bridges, and the minimum total cost is 0.

Since the company's budget is limited, he needs to find the minimum total cost to achieve this goal. Here, the total cost refers to the sum of the costs of the selected proposals.

If it is possible to connect all islands, output the minimum total cost (in ten-thousand yen) as an integer. If it is impossible, output -1.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq U_i \leq N
• 1 \leq V_i \leq N
• U_i \neq V_i
• 1 \leq C_i \leq 10^9
• All input values are integers

Sample Input 1

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

Sample Output 1

9

Sample Input 2

3 1
1 2 100

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

42

Problem Statement

Takahashi has N cards arranged in a horizontal row. Each card has a number from 1 to N written on it, and they are currently arranged in the order P_1, P_2, \ldots, P_N from left to right.

Takahashi aims to arrange the cards in ascending order of their numbers (i.e., 1, 2, \ldots, N from left to right). As a measure of how disordered the arrangement is, he uses the inversion count.

The inversion count of a card sequence Q_1, Q_2, \ldots, Q_N is the number of pairs (i, j) satisfying 1 \leq i < j \leq N such that Q_i > Q_j.

Takahashi can perform an operation where he selects two adjacent cards and swaps their positions. He can perform this operation at most K times, and in each operation, he is free to choose any adjacent pair to swap (the same pair may be chosen multiple times).

When Takahashi performs the operations optimally to minimize the inversion count, find the minimum inversion count of the card sequence that can be achieved after the operations.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq K \leq 10^{18}
• (P_1, P_2, \ldots, P_N) is a permutation of (1, 2, \ldots, N)
• All inputs are integers

Sample Input 1

5 2
3 1 4 5 2

Sample Output 1

2

Sample Input 2

3 100
3 2 1

Sample Output 2

0

Sample Input 3

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

Sample Output 3

12