컴퓨터 부품

이미지 출처: commons.wikimedia.org

Magni는 새 데스크톱 컴퓨터를 구매하려고 하며, 여기에는 어떤 부품을 사서 넣어야 하는가라는 중요한 문제가 따른다. 물론 그에게 무한한 돈이 있는 것은 아니므로, 쓸 수 있는 돈으로 가능한 최고의 성능을 얻는 일이 까다롭다. 현실에서는 서로 다른 부품이 서로 다른 작업에서 당연히 서로 다른 성능을 내지만, 단순화를 위해 주어진 부품의 평균 성능만 고려한다. 아주 비싸고 좋은 그래픽 카드를 사더라도 매우 좋지 않은 CPU를 산다면, 그래픽 카드는 성능이 낮은 CPU 때문에 병목 현상을 겪는다. 따라서 컴퓨터의 성능은 가장 성능이 낮은 부품의 성능에 불과하다. Magni가 살 수 있는 최고의 컴퓨터를 구매하도록 도와줄 수 있는가?

채점

그룹 | 점수 | 제한

1 | 20 | $1 \leq n \leq 1\,000$, 같은 종류인 두 부품은 없음

2 | 20 | $1 \leq n \leq 1\,000$, 모든 부품의 성능은 최대 $100\,000$

3 | 20 | $1 \leq n \leq 1\,000$, $k = 1$

4 | 20 | $1 \leq n \leq 1\,000$

5 | 20 | $1 \leq n \leq 100\,000$

첫째 줄에는 양의 정수 세 개 $n, k$와 $p$이 주어진다. 여기서 $n$은 구매 가능한 부품의 수이고, $k$는 서로 다른 부품 종류의 수이며, $p$은 Magni가 컴퓨터에 쓸 수 있는 금액이다. $1 \leq k \leq n$임이 보장된다. 다음 줄에는 부품 종류의 이름을 각각 나타내는 문자열 $k$개가 공백으로 구분되어 주어진다. 다음 $n$개의 줄은 각각 구매 가능한 부품 하나를 설명한다. 각 줄에는 문자열 $s$와 정수 두 개 $v, g$가 주어진다. 문자열은 부품의 종류를 나타내며, 항상 위 입력에서 주어진 $k$개 종류 중 하나이다. 값 $v$는 부품의 가격을 나타내며 $0 \leq v \leq 10^9$을 만족한다. 마지막으로 $g$는 부품의 성능을 나타내며 $0 \leq g \leq 10^9$을 만족한다. 컴퓨터에는 각 종류의 부품이 정확히 하나씩 들어가야 하며, 컴퓨터의 성능은 컴퓨터를 구성하는 $k$개 부품의 성능 값 중 최솟값이다.

입력의 모든 문자열은 최대 $10$개의 문자로 이루어지며 영문 소문자와 대문자만 포함한다. 입력에 있는 모든 문자열의 길이의 합은 최대 $6 \cdot 10^5$이다.

Magni가 가진 돈으로 달성할 수 있는 최고의 성능을 출력한다. 어떤 컴퓨터도 조립하기에 돈이 충분하지 않다면, 대신 O nei!을 출력한다.