문제

구르미는 얼마전 새로 구매한 자동차를 타고 여행을 떠나려고 한다. 구르미는 운전 실력이 서툴러 운전을 할 때 여유가 없어지지만, 이번에 새로 구매한 자동차에는 현대모비스의 자율 주행 기술이 탑재되어 있어 운전의 부담이 훨씬 덜해졌다.

그래서 구르미는 운전할 때 노래를 들을 수 있을 만큼의 여유가 생겼고, 오랜만에 가는 여행이니 최고의 플레이리스트를 만들어 여행길을 가는 동안 노래를 만끽하고 싶다.

구르미는 총 개의 곡을 가지고 있으며, 이 중 일부 노래를 뽑아 여행 중 들을 플레이리스트를 만들려고 한다. 구르미의 여행길은 정확히 분이 걸리고, 구르미는 여행을 시작할 때 노래를 듣기 시작해서 목적지에 도착했을 때 딱 모든 노래의 재생이 끝나면 한다. 따라서, 구르미의 플레이리스트에 속한 노래의 재생 시간 합은 정확히 분이 되어야 한다.

또, 구르미는 비슷한 제목으로 시작하는 노래들을 연달아 듣는 걸 좋아하기 때문에, 플레이리스트에 속한 노래의 제목들의 공통 접두사 길이가 최대한 길었으면 한다. 이 때 어떤 문자열 의 맨 앞에서 시작해서 연속한 임의의 개 글자를 골라 새로운 문자열을 만든 것을 의 접두사라고 하며, 문자열들이 주어졌을 때 모든 문자열이 공통으로 포함하는 접두사를 공통 접두사, 그리고 그 중 가장 길이가 긴 것을 최장 공통 접두사라고 한다. 예를 들어, 문자열 "happy", "has", "hack" 이 주어졌을 때 "h", "ha"는 세 문자열의 공통 접두사지만 "hac", "hap"등은 공통 접두사가 아니다. 또, 세 문자열의 최장 공통 접두사는 "ha"가 된다.

정리하자면, 구르미가 만들 플레이리스트는 아래의 조건을 만족해야 한다.

• 같은 노래는 플레이리스트에 최대 한 번만 들어갈 수 있다.
• 플레이리스트에 속한 노래들의 재생 시간 합이 정확히 여야 한다.
• 플레이리스트에 속한 노래 제목들의 최장 공통 접두사 길이를 가능한 한 길게 만들어야 한다.

조건을 만족하는 경우가 여러가지라면, 플레이리스트에 속한 노래들의 최장 공통 접두사가 사전순으로 최소가 되게 만들고 싶다.

예를 들어, 구르미의 여행 시간은 총 40분이고, 구르미는 아래의 7개 곡을 가지고 있다고 하자.

• liveforever : 16분
• happyending : 22분
• liveyoung : 24분
• happening : 18분
• liveforsomeone : 19분
• liveforyou : 5분
• goormio : 40분

이중 liveforever, liveyoung을 뽑아서 플레이리스트를 만드는 경우 총 길이가 40분이므로 조건을 만족하고, 이 때 최장 공통 접두사는 live가 된다.

그 외에도 liveforever, liveforsomeone, liveforyou를 뽑아서 플레이리스트를 만드는 것도 가능한데, 이 때 최장 공통 접두사는 livefor가 된다. 그리고 이 경우가 조건을 만족하는 플레이리스트 중 최장 공통 접두사의 길이가 가장 긴 경우이다. 

하지만 goormio 한 곡만으로도 조건을 만족하게 플레이리스트를 구성할 수 있고, 이 때 최장 공통 접두사는 goormio가 된다. 이 경우가 위의 플레이리스트와 최장 공통 접두사의 길이는 동일하나 사전순으로 goormio가 livefor보다 앞서기 때문에, 구르미는 goormio 한 곡으로 구성된 플레이리스트를 만들게 될 것이다.

구르미를 도와 이렇게 플레이리스트를 구성하는게 가능한지 판별하고, 가능하다면 조건을 만족하는 플레이리스트에 속한 노래들의 최장 공통 접두사를 출력하는 프로그램을 만들어보자.

입력

첫째 줄에 구르미가 가지고 있는 노래의 개수 과 여행 시간을 나타내는 정수 가 주어진다().

둘째 줄부터 줄에 걸쳐 구르미가 가진 번째 노래의 이름을 나타내는 문자열 와 해당 노래의 재생 시간을 나타내는 정수 가 주어진다(). 노래의 이름은 영문 소문자로만 구성되어 있으며, 구르미가 가진 모든 노래의 이름 길이의 합은 을 넘지 않는다. 

출력

첫째 줄에 조건을 만족하는 최대 공통 접두사의 길이와, 해당 접두사를 공백으로 구분하여 출력한다.

만약 조건을 만족하는 플레이리스트 구성 방법이 없다면, 을 출력하고 종료한다.

구름 블로그 방문하기

* 문제에 대한 힌트는 블로그에서 확인할 수 있습니다.

* 문제에 대한 질문은 Q&A에 남겨주세요!