최고 품질 전화번호 만들기

영식이는 새 휴대전화 번호를 친구들이 기억하기 쉽게 하이픈(-)으로 나누어 알려 주려고 한다. 전화번호는 숫자만으로 이루어진 길이 N의 문자열이며, 각 그룹은 반드시 숫자 2개 또는 3개로 이루어져야 한다.

각 그룹은 다음 세 종류 중 하나로 분류된다.

1. 오 그룹: 그룹 안의 모든 숫자가 같다. 예: 000, 77
2. 걍 그룹: 길이가 3이고, 세 숫자 중 정확히 두 숫자가 같다. 예: 030, 229, 116
3. 즐 그룹: 그룹 안의 모든 숫자가 서로 다르다. 예: 123, 90

전화번호의 품질은 다음 값으로 정한다.

2 * (오 그룹의 개수) + (걍 그룹의 개수)

주어진 전화번호를 위 규칙에 맞게 나누었을 때, 품질이 최대가 되는 전화번호 표기를 출력하시오.

첫째 줄에 영식이의 전화번호가 주어진다.

전화번호는 숫자 0부터 9까지만으로 이루어져 있으며, 길이는 2 이상 1,000 이하이다.

전화번호를 적절히 그룹으로 나누어 품질이 최대가 되는 표기를 출력한다.

각 그룹은 하이픈(-)으로 구분한다. 품질이 최대인 표기가 여러 개라면 사전순으로 가장 앞서는 것을 출력한다. 문자열 비교에서는 다음 순서를 사용한다.

- < 0 < 1 < 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9

첫 번째 공개 테스트의 전화번호는 여러 방식으로 나눌 수 있다.

• 508-86-38: 품질 0
• 50-886-38: 품질 1
• 50-88-638: 품질 2

따라서 품질이 가장 큰 표기는 50-88-638이다.