최대한 불공평하면서 공평한 IKEA 여행

이미지 출처: Wikimedia.org

Dagur와 친구들은 Faulty Komputerprogram(FK) 동아리에서 쓸 가구를 사러 IKEA에 갔지만, Dagur는 게을러서 가구를 먼 길 내내 들고 돌아가고 싶지 않다. 하지만 모두가 같은 수의 물건을 들어야 하며, 그렇지 않으면 불공평할 것이다. 따라서 Dagur는 가능한 한 적은 무게를 들기로 했다.

물건을 나르는 사람(Dagur와 친구들)의 수 $k$과 $n$개의 가구 및 각 가구의 무게 목록이 주어진다. Dagur가 무게를 최소화하려면 어떤 물건을 들어야 하는지 구한다.

사람의 수가 물건의 수를 반드시 나누어떨어지게 하지는 않으므로, 모두가 같은 수의 물건을 들 수 있는 것은 아니다. 이 경우 Dagur는 자신이 편하게 빠져나가려 한다는 것이 너무 명백해지지 않는 한 가능한 한 적은 수의 물건을 들려고 한다.

Dagur는 $\lfloor n/k \rfloor$개의 물건만 드는 것으로 넘어가려 한다. 유일한 예외는 이렇게 하면 그의 게으름이 명백해지는 경우이다. 이는 물건을 무게순으로 정렬했을 때 가장 가벼운 $\lceil n/k \rceil$개의 물건의 총무게가 그다음 $\lfloor n/k \rfloor$개의 물건의 총무게보다 엄격히 작은 경우에 해당한다. 이 경우 Dagur는 덜 명백하게 보이도록 $\lceil n/k \rceil$개의 물건을 든다.

$7$개의 물건이 있고 $3$명이 나르는 예를 살펴보자. 즉, $n = 7$이고 $k = 3$이다. 물건을 무게가 증가하는 순서로 정렬한 뒤 $x_1, x_2, \ldots, x_{7}$라고 부르면 $x_1 < x_2 < \cdots < x_{7}$이다. 그러면 Dagur는 $2$개의 물건을 들지만, $x_1 + x_2 + x_3 < x_4 + x_5$이면 대신 $3$개의 물건을 든다.

Dagur가 들 수 있는 가장 가벼운 물건 집합이 서로 다르게 여러 개라면, Dagur는 구매한 물건 목록에서 더 먼저 등장한 물건을 선택하여 동률을 해결한다.

채점

그룹 | 점수 | 제한 조건

1 | 25 | $1 \leq n,k \leq 10$, $k$은 $n$을 나눈다

2 | 25 | $1 \leq n,k \leq 10$

3 | 25 | $1 \leq n,k \leq 100\,000$, $k$은 $n$을 나눈다

4 | 25 | $1 \leq n,k \leq 100\,000$

입력은 여러 줄로 이루어진다. 첫째 줄에는 물건을 나르는 사람의 수를 나타내는 하나의 정수 $k$가 주어진다. 다음 줄에는 IKEA에서 구매한 제품의 수를 나타내는 하나의 정수 $n$이 주어진다. 그다음 $n$개의 줄에는 구매한 모든 제품의 목록이 주어지며, 각 줄에는 한 제품의 이름과 무게가 주어진다. 각 무게는 최대 $100\,000$이다. 각 이름은 최대 10개의 영문자로 이루어지고 공백이 없으며, 빈 이름도 없다.

첫째 줄에 Dagur가 어깨에 짊어지는 총무게를 출력한다. 그다음 줄부터는 Dagur가 어깨에 짊어지는 모든 물건을 알파벳순으로 한 줄에 하나씩 출력한다.