마이크로마스터 수료증
시간 제한1초메모리 제한2048 MB
ASCII 상자로 그려진 마이크로마스터 커리큘럼에서 세 개를 완성하는 데 필요한 서로 다른 과목 수의 최솟값을 구합니다.
문제
학과에서 교육과정이 있는 마이크로마스터를 여러 개 마련했다. 학생이 마이크로마스터의 모든 과목을 이수하면 그 마이크로마스터의 수료증을 받는다. 한 과목이 여러 마이크로마스터의 교육과정에 포함될 수 있다. 소로시는 수료증의 종류에는 관심이 없고 수료증을 받는 것만 생각한다. 그는 수강하는 과목 수를 최소로 하면서 마이크로마스터 수료증을 개 받으려고 한다. 교육과정은 게시판에 붙어 있다. 이 교육과정을 바탕으로 소로시가 목표를 이루도록 도와라.
입력
입력은 최대 행, 열의 게시판이다. 각 마이크로마스터 교육과정은 직사각형 상자 안에 들어 있다. 게시판의 테두리와 상자의 테두리는 모서리를 +, 가로변을 -, 세로변을 |로 나타낸다. 교육과정 상자끼리는 문자를 공유하지 않으며, 각 상자는 자신만의 테두리를 가진다. 상자 안의 각 줄에는 과목 이름이 최대 하나 있다. 과목 이름은 영문자, 숫자, 공백으로 이루어진다. 과목 이름은 대소문자를 구분하지 않으며 공백은 무시한다. 예를 들어 General math1과 generalMath 1은 같은 과목이다. 상자는 최대 개이고, 각 상자에는 과목이 최대 개 있다. 게시판에는 상자가 적어도 개 있고, 각 상자에는 과목이 적어도 개 있다.
출력
소로시가 수료증을 적어도 개 받기 위해 수강해야 하는 과목 수의 최솟값을 한 줄에 출력한다.