농장 품목별 출하 장부

문제

한 농장은 여러 작업 구역에서 모은 출하 기록을 하나의 장부로 합치려 한다. 작업자는 출하할 때마다 품목 코드와 상자 수를 기록한다. 같은 품목을 하루에 여러 번 출하할 수 있으므로 장부의 여러 행에 같은 코드가 나타날 수 있다. 장부의 행 순서는 작업자가 기록을 전달한 순서이며, 품목 코드나 상자 수의 순서와는 관계가 없다. 각 행은 품목 코드와 상자 수를 쉼표 하나로 연결한 CSV 형식이다. 이 문제에서 사용하는 CSV에는 머리글, 따옴표, 빈 필드, 필드 안의 쉼표가 없으며, 행 안에 공백도 없다. 품목 코드는 영문 대문자로만 이루어진 문자열이다. 코드가 완전히 같은 기록만 같은 품목으로 취급한다. 예를 들어 A와 AA는 서로 다른 품목이다. 농장 담당자는 먼저 각 품목의 모든 기록에 적힌 상자 수를 더해 품목별 총출하량을 구한다. 그다음 총출하량이 기준값 K 이상인 품목만 보고서에 남긴다. 기준값은 개별 행의 상자 수가 아니라 같은 품목의 상자 수를 모두 더한 결과에 적용한다. 상자 수가 0인 기록도 유효하며, 그러한 기록만 있는 품목도 장부에 등장한 품목으로 취급한다. 보고서에는 남은 품목의 코드와 총출하량을 한 줄에 하나씩 적는다. 품목은 총출하량이 큰 순서로 배치하고, 총출하량이 같으면 코드의 사전순으로 배치한다. 사전순에서는 영문 대문자의 알파벳 순서를 사용하며, 한 코드가 다른 코드의 접두사이면 짧은 코드가 먼저 온다. 보고서에 남는 품목이 하나도 없으면 대신 NONE을 출력한다. 주어진 장부를 처리하여 이 규칙에 맞는 보고서를 작성하는 프로그램을 만든다.

입력

첫째 줄에 기록 수 N과 기준값 K가 공백으로 구분되어 주어진다. N과 K는 정수이며 1≤N≤20,000, 0≤K≤200,000,000이다.
다음 N개 줄에는 코드,상자수 형식의 기록이 하나씩 주어진다. 코드는 길이가 1 이상 6 이하인 영문 대문자 문자열이고, 상자 수는 0 이상 10,000 이하의 정수이다. 상자 수는 불필요한 앞자리 0 없이 주어지며, 값이 0이면 0으로 주어진다. 같은 코드가 여러 번 등장할 수 있다.

출력

총출하량이 K 이상인 각 품목에 대해 코드와 총출하량을 공백 하나로 구분하여 한 줄에 출력한다. 총출하량의 내림차순으로 출력하고, 총출하량이 같으면 코드의 사전순으로 출력한다. 해당 품목이 없으면 NONE을 한 줄에 출력한다.

6 10
BEAN,7
APPLE,4
BEAN,5
CORN,12
APPLE,5
DILL,0

BEAN 12
CORN 12

3 1
A,0
A,0
B,0

NONE

3 0
AA,0
A,0
AA,0

A 0
AA 0

출처: Devin.KR 자체 제작