Bíókort

Arnar의 마지막 영화 카드.

아주 오래전 Bíótríó가 결성되었다. 원년 구성원은 Arnar, Hannes, Sara였다. 이 모임의 목표는 간단했다. 영화관에 자주, 저렴하게 가는 것이었다. 그들은 한 해에 백 번이 넘도록 영화관에 갔고, 때로는 그보다 더 자주 가기도 했다. 결성된 지 몇 년 뒤 Halldór가 모임에 합류하면서, 모임은 영화 사중주단이 되었다.

하지만 그들은 어떻게 파산하지 않으면서 그렇게 자주 영화관에 갈 수 있었을까? 답은 영화 카드다! Smárabíó는 한때 한 번 비용을 내면 이후 각 영화를 정확히 한 번씩 볼 수 있는 일 년짜리 카드를 판매했다. 이 카드는 특정 개인에게 귀속되지 않아, 여러 사람이 한 장의 영화 카드를 함께 사용할 수 있었다. 영화 카드가 할인될 때 구매함으로써, 이 모임은 어느 한 해에 표 한 장당 평균 비용을 단 $240$ ISK까지 낮출 수 있었다. 안타깝게도 이 상품은 더 이상 존재하지 않는다.

영화 사중주단은 영화를 거르는 것을 좋아하지 않았지만, 때로는 다른 사람들을 데려가기도 했다. 매년 그들은 누구를 영화관에 함께 데려갈 수 있을지 알아보았다. 심지어 각 영화가 정확히 얼마나 인기 있을지도, 다시 말해 각 영화를 보러 갈 모임 구성원이 몇 명인지도 알고 있었다.

그들은 한 해 동안의 표 비용을 어떻게 최소화했을까?

채점

그룹 | 점수 | 제한 조건

1 | 10 | $1 \leq n \leq 1\,000$, $m = 0$, $k = 0$.

2 | 10 | $1 \leq n \leq 1\,000$, $m = 0$.

3 | 10 | $1 \leq n \leq 1\,000$, $k = 0$.

4 | 10 | $1 \leq n \leq 1\,000$.

5 | 10 | $1 \leq n \leq 200\,000$, 모든 영화의 인기도가 같다.

6 | 10 | $1 \leq n \leq 200\,000$, 각 인기도는 적어도 $0$이고 최대 $999$이다.

7 | 20 | $1 \leq n \leq 200\,000$, 서로 다른 인기도는 최대 $1\,000$개이다.

8 | 20 | $1 \leq n \leq 200\,000$.

입력의 첫째 줄에는 세 정수 $n$, 올해 영화관에서 상영하는 영화의 수, $m$, 일회용 표 한 장의 가격, 그리고 $k$, 일 년 전체에 사용할 수 있는 영화 카드의 가격이 주어지며, 두 가격은 모두 ISK 단위로 주어진다. 마지막으로 각각 하나의 영화를 설명하는 $n$개의 줄이 주어진다. 각 영화는 이름과 인기도가 공백으로 구분되어 주어진다.

각 영화의 이름은 서로 다르며, 적어도 $1$자이고 최대 $20$자인 영문자 또는 숫자로 이루어진다. 항상 $0 \leq m \leq 100\,000$이고 $0 \leq k \leq 10\,000\,000$임이 보장된다. 각 인기도는 적어도 $0$이고 최대 $10^6$이다.

비용이 최소가 되도록 카드 수를 최적으로 선택했을 때, 구매해야 하는 영화 카드의 수와 한 해 동안 모든 영화를 보는 데 드는 총비용을 ISK 단위로 출력한다. 정답이 여러 개라면 그중 아무거나 출력해도 된다. 매년 발행되는 영화 카드는 $10^6$장뿐이므로, 구매할 수 있는 카드 수도 최대 그만큼임에 유의한다.