시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1 1 1 100.000%

문제

성냥 팔이 소녀 숌은 추위에 덜덜떨며 거리에 많은 성냥을 가지고 앉아있다. 숌은 사람들이 자신의 성냥을 사지 않고 그냥 지나치기만 하자, 성냥을 이용해서 숫자를 만들기로 결심했다.

원룡이가 운영하는 가게에서는 성냥 몇 개를 숫자 장난감으로 바꿔준다. 모든 숫자가 있는 것은 아니고, 원룡이가 그날 좋아하는 숫자만 무한대로 가지고 있다.

만약 숫자 0으로 바꾸기 위해선 6개의 성냥이 필요하고, 숫자 1로 바꾸고 위해서는 7개의 성냥이, 숫자 2로 바꾸려면 8개의 성냥이 필요하다고 하고, 지금 숌이 성냥이 21개가 있으면, 숌이 만들 수 있는 가장 큰 숫자는 210(8+7+6) 이다.

숌은 현재 자기가 가지고 있는 성냥중 몇 개를 원룡이의 가게에서 숫자 장난감으로 바꾸려고 한다. 그 다음에 그 장난감을 이용해서 가장 큰 숫자를 만드려고 한다.

숌이 현재 가지고 있는 성냥의 개수와, 원룡이의 가게에서 숫자 장난감과 성냥의 교환 비율이 주어진다. 교환 비율이란 숫자 장난감 1개 = 성냥 x개 일 때 x를 말한다. 그 때, 숌이 만들 수 있는 가장 큰 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 현재 원룡이의 가게에 있는 숫자의 개수 N이 주어진다. 둘째 줄부터 총 N개의 줄에 A B와 같이 두 개의 숫자가 주어진다. 그 의미는 A라는 숫자 장난감으로 바꾸는데 성냥 B개가 들어간다는 소리다. A는 중복되지 않게 들어오며, 0보다 크거나 같고, 9보다 작거나 같다. B는 10^18보다 작거나 같은 자연수이다. 입력으로 주어지지 않는 숫자는 사용할 수 없다. 마지막 줄에는 숌이가 현재 가지고 있는 성냥의 개수가 주어진다. 성냥의 개수는 0보다 크거나 같고, 10^18보다 작거나 같은 정수이다.

출력

첫째 줄에 숌이가 만들 수 있는 가장 큰 수의 자리수를 출력한다. 둘째 줄에 숌이가 만들 수 있는 가장 큰 수의 처음 50자리를 출력하고, 셋째 줄에는 숌이가 만들 수 있는 가장 큰 수의 마지막 50자리를 출력한다. 만들 수가 없다면 자리수에 0을 출력하고 둘째줄과 셋째줄에는 아무것도 출력하면 안된다.

예제 입력

3
0 6
1 7
2 8
21

예제 출력

3
210
210

힌트

출처