The Department of Computer Engineering has provided several micromasters, each containing a curriculum. If a student successfully completes all the courses of a micromaster, he will receive the certificate of that micromaster. A course may be included in the curriculum of several micromasters.
Soroush, who only thinks about getting a certificate and doesn’t care about the type of certificate, wants to get micromasters certificates by taking the minimum possible number of courses. The micromasters curriculums are posted on the bulletin board. Help Soroush reach his goal according to the micromasters curriculums.
The input represents a bulletin board. The board consists of at most rows and columns. Each micromasters curriculum is encapsulated in a rectangular box. The boundaries of the bulletin board and the curriculum boxes are represented by characters “+”
, “-”
, and “|”
for corners, horizontal sides, and vertical sides, respectively. The curriculum boxes are disjoint (with no characters in common) and each has its own boundary. Each line inside a curriculum box contains at most one course name.
Course names consist of alphanumeric and space characters. Course names are not case-sensitive, and spaces do not matter in them. For example, “General math1” and “generalMath 1” are the same.
There are at most curriculum boxes and each box contains at most courses. It is guaranteed that there are at least boxes on the board and there is at least course in each box.
Print a single line containing the minimum number of courses that should be taken by Soroush to get at least 3 certificates.