Есть \(n\) работников и \(m\) заданий. Работники пронумерованы от \(1\) до \(n\). У каждого задания \(i\) есть значение \(a_i\) — номер работника, который специализируется на этом задании.
Каждое задание должен выполнить один из работников. Если работник специализируется на задании, то он выполняет его за \(1\) час. Иначе он тратит на него \(2\) часа.
Работники работают параллельно и независимо друг от друга. Каждый работник может одновременно работать только над одним заданием.
Назначьте работника на каждое задание так, чтобы все задания были завершены как можно раньше. Работа начинается в момент времени \(0\). К какому минимальному времени все задания могут быть завершены?
Выходные данные
На каждый набор входных данных выведите одно целое число — минимальное время, к которому все задания могут быть завершены.
Примечание
В первом наборе первый работник работает над заданиями \(1\) и \(3\), а второй — над заданиями \(2\) и \(4\). Так как они оба специализируются на соответствующих заданиях, они их выполняют по \(1\) часу. Оба они выполняют \(2\) задания за \(2\) часа. Поэтому все задания оказываются выполнены за \(2\) часа.
Во втором наборе оптимально дать первому работнику задания \(1, 2\) и \(3\), а второму — задание \(4\). Первый работник потратит \(3\) часа, второй — \(2\) часа (так как он не специализируется на взятом задании).
В третьем наборе каждый работник может работать над заданием, на котором он специализируется. Так они выполнят все задания за \(1\) час.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 4
1 2 1 2
2 4
1 1 1 1
5 5
5 1 3 2 4
1 1
1
|
2
3
1
1
|