1426번 - 카드 넣기

세준이는 N장의 카드를 가지고 있다. 각각의 카드에는 정수가 쓰여 있고, 문자도 하나 쓰여져 있다. 그리고, 세준이는 카드를 넣을 수 있는 통을 하나 가지고 있다.

세준이는 카드를 아무렇게나 통에 넣고는 했는데, 어느 날 다솜이가 세준이의 카드 통에 정수를 써놓고 도망갔다.

세준이는 정말 화가 나서 정수를 지우고 싶었지만, 지우는 방법을 몰라서 새로운 규칙을 만들어서 카드를 통에 넣으려고 한다.

카드를 통에 넣는 방법은 다음과 같다. 일단 카드 한 장을 고른다. 그리고 카드에 쓰여져 있는 번호보다 작거나 같은 통에 카드를 넣는다.

이렇게 카드를 넣는 방법은 여러 가지가 존재한다. 하지만 세준이는 앞에서부터 차례대로 카드에 쓰여져 있는 문자를 문자열로 만들어서 그 문자열이 가장 사전 순으로 앞서는 문자열을 알고 싶어한다.

예를 들면, 카드가 세 장이 있다. (1, A), (2, B), (3, C)가 있다. 그리고 통에 쓰여져 있는 정수는 2 2 1 이다. 그럼 일단 첫 번째 통에 2번 카드를 넣고, 두 번째 통에 3번 카드를 넣고, 세 번째 통에 1번 카드를 넣으면, 문자열은 BCA가 돼서 규칙에 맞게 넣으면서 가장 사전순으로 빠른 문자열이 나온다.

세준이가 가지고 있는 카드와 통에 쓰여져 있는 정수가 주어졌을 때, 사전순으로 가장 빠른 문자열을 구하는 프로그램을 작성하시오.

첫째 줄에 세준이가 가지고 있는 카드의 개수 N이 주어진다. 이 값은 50보다 작거나 같은 자연수이다. 둘째 줄에는 세준이가 가지고 있는 카드의 정보가 한 줄에 하나씩 주어진다. 카드의 정보는 정수와 문자 하나가 공백을 사이에 두고 주어진다. 정수는 1,000보다 작거나 같은 자연수이고, 문자는 알파벳 대문자이다. 마지막 줄에는 통에 쓰여 있는 정수가 공백을 사이에 두고 주어진다. 이 값은 1,000보다 작거나 같다.

첫째 줄에 사전순으로 제일 빠른 문자열을 출력한다. 만약 규칙대로 통에 넣을 수 없으면 -1을 출력한다.