Problem Statement

In a parallel universe, AtCoder holds AtCoder Big Contest, where 10^{16} problems are given at once.
The IDs of the problems are as follows, from the 1-st problem in order: A, B, ..., Z, AA, AB, ..., ZZ, AAA, ...

In other words, the IDs are given in the following order:

• the strings of length 1 consisting of uppercase English letters, in lexicographical order;
• the strings of length 2 consisting of uppercase English letters, in lexicographical order;
• the strings of length 3 consisting of uppercase English letters, in lexicographical order;
• ...

Given a string S that is an ID of a problem given in this contest, find the index of the problem. (See also Samples.)

Constraints

• S is a valid ID of a problem given in AtCoder Big Contest.

Sample Input 1

AB

Sample Output 1

28

The problem whose ID is AB is the 28-th problem of AtCoder Big Contest, so 28 should be printed.

Sample Input 2

C

Sample Output 2

3

The problem whose ID is C is the 3-rd problem of AtCoder Big Contest, so 3 should be printed.

Sample Input 3

BRUTMHYHIIZP

Sample Output 3

10000000000000000

The problem whose ID is BRUTMHYHIIZP is the 10^{16}-th (last) problem of AtCoder Big Contest, so 10^{16} should be printed as an integer.

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1 to N, and the i-th edge connects vertex A_i and vertex B_i. Let us delete zero or more edges to remove cycles from the graph. Find the minimum number of edges that must be deleted for this purpose.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N
• The given graph is simple.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

2

One way to remove cycles from the graph is to delete the two edges between vertex 1 and vertex 2 and between vertex 4 and vertex 5.
There is no way to remove cycles from the graph by deleting one or fewer edges, so you should print 2.

Sample Input 2

4 2
1 2
3 4

Sample Output 2

0

Sample Input 3

5 3
1 2
1 3
2 3

Sample Output 3

1

Problem Statement

KEYENCE has N departments, where A_i employees belong to the i-th department (1 \leq i \leq N). No employee belongs to multiple departments.

The company is planning cross-departmental projects. Each project will be composed of exactly K employees chosen from K distinct departments.

At most how many projects can be made? No employee can participate in multiple projects.

Constraints

• 1 \leq K \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^{12}
• All values in input are integers.

Sample Input 1

3 3
2 3 4

Sample Output 1

2

There can be two projects, each composed of three employees from distinct departments.

Sample Input 2

4 2
1 1 3 4

Sample Output 2

4

Sample Input 3

4 3
1 1 3 4

Sample Output 3

2

Problem Statement

Takahashi has come to an amusement park.
The park has N attractions. The fun of the i-th attraction is initially a_i.

When Takahashi rides the i-th attraction, the following sequence of events happens.

• Takahashi's satisfaction increases by the current fun of the i-th attraction.
• Then, the fun of the i-th attraction decreases by 1.

Takahashi's satisfaction is initially 0. He can ride the attractions at most K times in total in any order.
What is the maximum possible value of satisfaction Takahashi can end up with?

Other than riding the attractions, nothing affects Takahashi's satisfaction.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq K \leq 2 \times 10^9
• 1 \leq A_i \leq 2 \times 10^9
• All values in input are integers.

Sample Input 1

3 5
100 50 102

Sample Output 1

502

Takahashi should ride the first attraction twice and the third attraction three times.
He will end up with the satisfaction of (100+99)+(102+101+100)=502.
There is no way to get the satisfaction of 503 or more, so the answer is 502.

Sample Input 2

2 2021
2 3

Sample Output 2

9

Takahashi may choose to ride the attractions fewer than K times in total.

Problem Statement

For two sets of integers, A and B, such that A \cap B = \emptyset, we define f(A,B) as follows.

• Let C=(C_1,C_2,\dots,C_{|A|+|B|}) be a sequence consisting of the elements of A \cup B, sorted in ascending order.
• Take k_1,k_2,\dots,k_{|A|} such that A=\lbrace C_{k_1},C_{k_2},\dots,C_{k_{|A|}}\rbrace. Then, let \displaystyle f(A,B)=\sum_{i=1}^{|A|} k_i.

For example, if A=\lbrace 1,3\rbrace and B=\lbrace 2,8\rbrace, then C=(1,2,3,8), so A=\lbrace C_1,C_3\rbrace; thus, f(A,B)=1+3=4.

We have N sets of integers, S_1,S_2\dots,S_N, each of which has M elements. For each i\ (1 \leq i \leq N), S_i = \lbrace A_{i,1},A_{i,2},\dots,A_{i,M}\rbrace. Here, it is guaranteed that S_i \cap S_j = \emptyset\ (i \neq j).

Find \displaystyle \sum_{1\leq i<j \leq N} f(S_i, S_j).

Constraints

• 1\leq N \leq 10^4
• 1\leq M \leq 10^2
• 1\leq A_{i,j} \leq 10^9
• If i_1 \neq i_2 or j_1 \neq j_2, then A_{i_1,j_1} \neq A_{i_2,j_2}.
• All input values are integers.

Sample Input 1

3 2
1 3
2 8
4 6

Sample Output 1

12

S_1 and S_2 respectively coincide with A and B exemplified in the problem statement, and f(S_1,S_2)=1+3=4. Since f(S_1,S_3)=1+2=3 and f(S_2,S_3)=1+4=5, the answer is 4+3+5=12.

Sample Input 2

1 1
306

Sample Output 2

0

Sample Input 3

4 4
155374934 164163676 576823355 954291757
797829355 404011431 353195922 138996221
191890310 782177068 818008580 384836991
160449218 545531545 840594328 501899080

Sample Output 3

102