Problem Statement

Takahashi is playing an online game. His current score is A points. To reach the top of the rankings, he needs a score of at least B points.

The only way for Takahashi to increase his score is by purchasing "Score Boosters" from the in-game item shop. Each Score Booster costs C coins, and each one purchased increases his score by 1 point. He can purchase any number of Score Boosters, including 0.

Find the minimum number of coins required to bring Takahashi's score to at least B points.

Note that if his current score is already at least B points, he does not need to purchase any Score Boosters, so the answer is 0.

Constraints

• 1 \leq A \leq 10^9
• 1 \leq B \leq 10^9
• 1 \leq C \leq 10^9
• All inputs are integers

Sample Input 1

50 100 3

Sample Output 1

150

Sample Input 2

150 100 5

Sample Output 2

0

Sample Input 3

999999000 1000000000 100

Sample Output 3

100000

Problem Statement

Takahashi is the student council president of a school. There are N students in this school, each assigned a student number from 1 to N.

This school has a system where students can send "friend requests" to each other. Friend requests are one-directional. That is, a friend request from student u to student v and a friend request from student v to student u are treated as different requests — it is possible for only one of them to exist, or for both to exist simultaneously.

Currently, M friend requests have been sent. The i-th friend request (1 \leq i \leq M) was sent from student A_i to student B_i.

Takahashi is planning an event for the school festival where students participate in pairs. Only pairs of students who have mutually sent friend requests to each other can participate in this event. Here, students u and v "have mutually sent friend requests to each other" means that both a friend request from student u to student v and a friend request from student v to student u exist.

For Takahashi, find the number of pairs of students who have mutually sent friend requests to each other. Note that the pair of student u and student v and the pair of student v and student u are considered the same pair and counted as 1.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N (1 \leq i \leq M)
• A_i \neq B_i (no friend request to oneself)
• If i \neq j, then (A_i, B_i) \neq (A_j, B_j) (there is at most one friend request from the same student to the same student)
• All input values are integers

Sample Input 1

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

Sample Output 1

2

Sample Input 2

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

Sample Output 2

3

Sample Input 3

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

Sample Output 3

5

Problem Statement

Takahashi is going to organize a chess elimination tournament. N players participate in this tournament, each numbered from 1 to N. Each player i has a rating S_i, and all players have distinct ratings.

In the tournament, matches are repeated until only 1 player remains. In each match, 2 players who have not yet been eliminated are chosen to compete against each other in a one-on-one match. The player with the higher rating always wins, and the losing player is eliminated from the tournament. Therefore, a total of N - 1 matches are held throughout the tournament.

Takahashi, as the organizer, is free to decide which 2 players compete in each match. Since Takahashi knows all players' ratings in advance and can perfectly predict the outcome of every match, he can optimally plan all match pairings before the tournament begins.

Takahashi has a player he is rooting for: player K. Takahashi wants to optimally arrange the match pairings to maximize the number of matches that player K wins. Player K will lose and be eliminated if matched against a player with a higher rating, after which their win count can no longer increase.

Determine the maximum number of matches player K can win.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq K \leq N
• 1 \leq S_i \leq 10^9
• All S_i are distinct
• All inputs are integers

Sample Input 1

4 3
5 1 3 2

Sample Output 1

2

Sample Input 2

5 2
3 10 7 1 5

Sample Output 2

4

Sample Input 3

10 5
20 50 10 5 30 80 15 25 40 60

Sample Output 3

5

Problem Statement

Takahashi has been put in charge of urban planning for a certain region. This region has N cities, each numbered from 1 to N.

The position of each city i (1 \leq i \leq N) is represented by integer coordinates in M-dimensional space, where A_{i,k} denotes the coordinate value in the k-th dimension (1 \leq k \leq M).

Takahashi defines the distance between two cities using the Manhattan distance. That is, the distance between city i and city j is \displaystyle\sum_{k=1}^{M} |A_{i,k} - A_{j,k}|.

Takahashi wants to compute the distances for all unordered pairs of distinct cities and find their total sum.

Specifically, compute the following value:

\sum_{1 \leq i < j \leq N} \sum_{k=1}^{M} |A_{i,k} - A_{j,k}|

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 10
• -10^6 \leq A_{i,k} \leq 10^6
• N, M, A_{i,k} are all integers
• It is guaranteed that the answer fits in a signed 64-bit integer (a non-negative integer at most 2^{63} - 1)

Sample Input 1

3 2
1 2
4 6
7 1

Sample Output 1

22

Sample Input 2

2 1
3
10

Sample Output 2

7

Sample Input 3

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

Sample Output 3

146

Sample Input 4

10 4
100 -200 300 -400
-150 250 -350 450
200 -100 400 -300
-250 150 -450 350
300 -300 200 -200
-100 400 -100 500
50 -50 150 -150
-350 350 -250 250
400 -400 100 -100
-200 200 -300 300

Sample Output 4

62500

Sample Input 5

2 1
-1000000
1000000

Sample Output 5

2000000

Problem Statement

Takahashi has been put in charge of shift management as the store manager at his part-time job. Next week, there are N time slots for which he wants to assign staff.

There are M part-time staff candidates, numbered from 1 to M. For each time slot i (1 \leq i \leq N), K_i candidate numbers who are available to work during that time slot are given. Specifically, the candidates available for time slot i are numbered C_{i,1}, C_{i,2}, \ldots, C_{i,K_i}.

For each time slot, Takahashi chooses either to assign exactly one candidate who is available for that time slot, or to assign no one. However, the same candidate cannot be assigned to multiple time slots. That is, each candidate can be assigned to at most one time slot.

Find the maximum number of time slots to which a candidate can be assigned.

Constraints

• 1 \leq N \leq 100
• 1 \leq M \leq 100
• 0 \leq K_i \leq M (1 \leq i \leq N)
• 1 \leq C_{i,j} \leq M (1 \leq i \leq N, 1 \leq j \leq K_i)
• For each i, C_{i,1}, C_{i,2}, \ldots, C_{i,K_i} are all distinct
• All input values are integers

Sample Input 1

3 3
2 1 2
2 2 3
2 1 3

Sample Output 1

3

Sample Input 2

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

Sample Output 2

4

Sample Input 3

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

Sample Output 3

5