Buffered Buffet

Time limit1sMemory limit1024 MB

Summary

Place n people around a circular table, each with a minimum required distance to every other person measured along the circumference, and find the smallest possible circumference.

Level: Medium6 of 10
Topics: Greedy, Sorting, Math, Two pointers
Solved: No attempts yet

Problem

Finally, you are allowed again to invite your friends over for a delicious buffet! However, you still need to take social distancing measures into account. To complicate matters further, your friends are coming from various different countries. Each of these countries has slightly different social distancing rules. For example, your friends from the US are required to sit at least $2$ meters from another person, while your friends from France only need to sit $1$ meter apart from others.

You would like for all your friends to sit around one large circular table. You want to position your friends at this table in such a way that everyone complies with the social distancing requirements of their respective country. To make matters a bit easier, the distance between two people sitting at the table is calculated along the circumference. What is the minimum circumference of the table such that everyone can comply with their social distancing requirement?

Input

The input consists of:

One line containing an integer $n$ ( $2 \le n \le 10^{5}$ ), the number of people sitting at the table (yourself included).
One line containing $n$ integers $d\_1, \dots, d\_n$ ( $1 \le d\_i \le 10^{9}$ ), how many meters each person needs to sit apart from others (measured along the circumference of the table).

Output

Output the minimum circumference of the table in meters such that everyone can sit at the table while respecting their social distancing measures.

Examples2

Example 1
Input
```
2
2 3
```
Expected output
```
6
```
Example 2
Input
```
3
2 2 3
```
Expected output
```
8
```