레이팅 미적용설명
베시(Bessie)는 비디오 게임을 하고 있다! 이 게임에서 유효한 버튼은 'A', 'B', 'C' 세 글자뿐이다. 베시는 원하는 순서대로 버튼을 누를 수 있지만, 가능한 콤보는 N개 (1 <= N <= 20)의 서로 다른 콤보뿐이다. 콤보 i는 길이가 1 이상 15 이하이고 'A', 'B', 'C'로만 이루어진 문자열 S_i로 표현된다.
베시가 콤보와 일치하는 글자 조합을 누를 때마다, 그 콤보로 1점을 얻는다. 콤보들은 서로 겹칠 수 있고, 심지어 동시에 끝날 수도 있다! 예를 들어 N = 3이고 가능한 세 콤보가 "ABA", "CB", "ABACB"일 때 베시가 "ABACB"를 누르면, 최종적으로 3점을 얻는다. 베시는 같은 콤보로 여러 번 점수를 얻을 수도 있다.
물론 베시는 최대한 빨리 점수를 얻고 싶어 한다. 베시가 정확히 K번 (1 <= K <= 1,000) 버튼을 누른다면, 얻을 수 있는 최대 점수는 얼마인가?
제약
입력 형식
첫째 줄: 공백으로 구분된 두 정수 N과 K.
둘째 줄부터 N+1번째 줄까지: i+1번째 줄에 콤보 i를 나타내는 문자열 S_i만 주어진다.
출력 형식
베시가 얻을 수 있는 최대 점수를 나타내는 정수 하나.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
combos.in · 출력을 쓸 파일 combos.out예제 1
입력
3 7
ABA
CB
ABACB출력
4설명
Output details: The optimal sequence of buttons in this case is ABACBCB, which gives 4 points--1 from ABA, 1 from ABACB, and 2 from CB.
문제 정보
태그