← К соревнованиям

Sort Me Round

Задача про Sort Me

Сложность: 31%

А вы знали, что Sort Me работает на основе своей собственной проверяющей системы nojudge? Давайте смоделируем типичную ситуацию в её работе.

Итак, у nojudge есть nn проверяющих серверов. Сервера проверяют решения последовательно: если вы отправите на один сервер три решения, которые проверяются a,ba, b и cc секунд соотвественно, то этот сервер освободится через a+b+ca + b + c секунд.

Вдруг mm участников контеста осенило, и они практически одновременно сдали каждый по одному решению. Благодаря АСОКПЛОХ (Алгоритм Скоростного Определения, Когда Программу Лучше Остановить к Х**м) вы заранее знаете, сколько секунд каждая из программ будет тестироваться.

nojudge распределяет нагрузку по серверам следующим образом:

  1. Выбирает из очереди решений то, которое будет проверяться дольше всего. Если таких несколько, выбирает случайное из них.
  2. Выбирает самый разгруженный сервер. Если таких несколько, выбирает случайный из них.
  3. Отправляет выбранное решение на выбранный сервер.
  4. Если в очереди остались решения, переходит к шагу 1.

Вам нужно смоделировать работу nojudge и выяснить, сколько времени потребуется серверам, чтобы проверить все решения после того, как nojudge распределит их по серверам (считайте, что распределение происходит моментально). Иными словами, сколько секунд пройдёт, прежде чем все nn серверов протестируют все mm решений.

Входные данные

В первой строке содержатся два числа nn и mm (1n,m1051 \le n, m \le 10^5), записанные через пробел. Во второй строке записано mm чисел a1,a2,,ama_1,a_2,…,a_m, где aia_i – это количество секунд, которое будет проверяться ii-тое решение. (1ai1051 \le a_i \le 10^5)

Выходные данные

Выведите одно число - минимально возможное количество секунд, через которое могут освободиться все проверяющие сервера.

Подзадачи

баллынеобх. подзадачиограничения
1

18

-

n,m3000n, m \leq 3000

2

20

-

n20n \leq 20

3

62

1, 2

Нет дополнительных ограничений

STDINSTDOUT
2 4
2 6 10 5
12
3 7
5 1 4 2 2 2 5
7

Примечание

В реальности nojudge, конечно, распределяет нагрузку иначе. Или всё-таки так же? Или нет? Или я просто отвлекаю вас от решения задачи? Ааа-а-а!