영화 보러 가자

Acmestan의 대가족이 즐기는 취미는 다 함께 영화를 보러 가는 것이다. 여러 세대로 이루어진 대가족이 함께 영화관을 찾는 모습은 흔한 일이다. Acmestan의 영화관에서는 두 종류의 표를 판다. 낱장 표(single ticket)는 정확히 한 사람이 입장할 수 있고, 가족 표(family ticket)는 부모 한 명과 그 자녀들이 함께 입장할 수 있다. 가족 표는 언제나 낱장 표보다 비싸며, 때로는 낱장 표의 다섯 배에 이르기도 한다.

어떤 표 조합이 가장 저렴한지 정하는 일은 꽤 까다롭다. 예를 들어 그림에 나온 가족은 네 가지 방법 중에서 고를 수 있다. 낱장 표 일곱 장, 가족 표 두 장, 가족 표 한 장(adam, bob, cindy용)과 나머지 네 명의 낱장 표, 또는 가족 표 한 장(bob과 그의 네 자녀용)과 남은 두 명의 낱장 표이다.

모든 사람이 입장할 수 있는 가장 저렴한 표 조합을 구하는 프로그램을 작성하라. 비용이 같은 조합이 여러 개라면 표의 개수가 가장 적은 조합을 택한다.

입력은 하나 이상의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 두 양의 정수 $S$와 $F$가 주어지며, 각각 낱장 표와 가족 표의 가격이다. 그다음 줄들은 혼자 온 사람의 이름이거나 다음 형태이다.

N1 N2 N3 ... Nk

여기서 $N_1$은 부모이고 $N_2, \ldots, N_k$는 그 자녀들이다. 모든 이름은 소문자 알파벳으로만 이루어지며 길이는 1000자 이하이다. 어떤 부모도 자녀를 1000명보다 많이 데려오지 않는다. 이름은 서로 겹치지 않으며, 한 이름은 최대 두 번(부모로 한 번, 자녀로 한 번) 나타난다. 각 테스트 케이스에는 최소 1명, 최대 100000명이 등장한다.

한 테스트 케이스는 다음 테스트 케이스가 시작되는 줄(두 정수로 이루어진 줄)에서 끝난다. 마지막 테스트 케이스 뒤에는 두 개의 0이 적힌 줄이 온다.

각 테스트 케이스마다 다음 형식으로 한 줄을 출력한다.

k. NS NF T

여기서 $k$는 테스트 케이스 번호(1부터 시작), $NS$는 낱장 표의 개수, $NF$는 가족 표의 개수, $T$는 전체 비용이다. 각 값은 하나의 공백으로 구분한다.