### PROBLEM LINK:

**Author:** Vitaliy Herasymiv

**Tester:** Hiroto Sekido

**Editorialist:** Anton Lunyov

### DIFFICULTY:

EASY

### PREREQUISITES:

Greedy algorithm, Sorting algorithms

### PROBLEM:

The best described in the problem itself.

### QUICK EXPLANATION:

The solution is based on several simple observations:

- Let
**M**be the total number of bands among all songs. - The first
**M**songs should be of different bands. Otherwise we can swap some songs and the sweetness will increase. - The lengths of first songs are multiplied by smaller numbers, hence it is advantageous to listen first
**M**songs from the shortest to the longest. - Also for the first
**M**songs we should choose the shortest song from each band. Otherwise swapping some songs we could increase sweetness. - These rules uniquely determine the answer (see details below).

Here we only mention that maximal value of the answer is about **5e18** and fits into signed 64bit integer type. Indeed, the maximal answer will be when there are **1e5** songs, all bands among them are different and each song has length **1e9**. Then the total sweetness is

**1e9 + 2 * 1e9 + 3 * 1e9 + … + 1e5 * 1e9 ≅ 1e5 * 1e5 / 2 * 1e9 = 5e18**,

while **2 ^{63}** is slightly larger than

**9e18**.

### EXPLANATION:

Here we describe in detail IMHO the simplest implementation of the above solution.

We store initial data as an array of pairs `a[]`

with lexicographical ordering. We denote the first element in pair as `B`

and the second as `L`

. After input the songs we sort them. So they will be sorted by band, and songs with the same band sorted by length in increasing order. Thus, the beginning of the solution looks as follows:

```
for i = 1 to N do
read a*.B, a*.L
sort a
```

Next we do one iteration over this array and count the number of different bands, form the list of shortest songs for each band and calculate the total length of the remaining songs:

```
songs = {}
total = 0
for i = 1 to N do
if i = 1 or a[i-1].B < a*.B then
add a*.L to songs
else
total = total + a*.L
M = size of songs
```

Why such simple loop does the job?

Note that when `i = 1`

or `a[i-1].B < a*.B`

then the song `a*`

is the shortest song for the band `a*.B`

and hence we add it to the list of songs played first. While otherwise it is the song that will be played after the first **M** songs and hence its length should be multiplied by **M**, so we just need to find the total length of all such songs.

Finally we sort the list `songs`

and calculate the sweetness for it by definition and also add `M * total`

to this value to get the answer:

```
ans = M * total
for i = 1 to M do
ans = ans + i * songs*
```

Refer to the editorialist’s solution as a good reference to this implementation.

### ALTERNATIVE SOLUTION:

There exists of course many other different implementations of the above solution.

See, for example, the tester’s solution.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be provided soon.

Tester’s solution can be found here.

Editorialist’s solution can be found here.

### RELATED PROBLEMS:

Will be provided soon. All readers are welcomed to provide related problems in comments.