У мальчика Вити скоро день рождения, который он хочет провести с друзьями. Какой же праздник без праздничной олимпиады? Для своих друзей Витя подготовил олимпиаду по программированию.
Когда все гости собрались, именинник распределил их по
m
командам. Витя очень старался сбалансировать силы команд, и у него это получилось. Каждую из предложенных
n
задач олимпиады любая команда решает ровно за
a
i
минут и всегда с первой попытки. Ребята не любят распыляться, поэтому если команда берется писать задачу
i
, то все ее участники непрерывно решают задачу в течении
a
i
минут. При этом команда может начинать решать следующую задачу сразу после того, как решила предыдущую.
Однако, Витя не хотел поссорить своих друзей, поэтому исключил элемент борьбы между командами — команды не соперничают, а помогают друг другу. Целью команд на олимпиаде является решение всех задач. Таким образом каждую задачу решает только одна команда. При этом друзьям засчитывается штрафное время, равное числу минут, прошедших от начала олимпиады до момента сдачи задачи. Единственная цель, которую преследуют друзья — сдать все задачи с наименьшим суммарным штрафным временем.
Например, пусть участвуют две команды, которым предложено в олимпиаде три задачи с временами решения 5, 10 и 15 минут. Пусть первая команда решает сначала вторую, а потом первую задачу. Таким образом за решение второй задачи друзья получат 10 штрафных минут, а за решение первой 15. Вторая команда с начала олимпиады решает только третью задачу, за которую друзья получат 15 штрафных минут. В сумме друзья Вити получат 40 штрафных минут.
В то время, когда друзья будут решать задачи, Витя будет управлять порядком, в котором команды будут их решать. Помогите Вите — напишите программу, которая вычислит наименьшее суммарное штрафное время, требуемое для сдачи всех задач.
