Under construction

Still being built. Things may change

Micromasters Certificates

Time limit1sMemory limit2048 MB

Summary
Given micromaster curriculums drawn as ASCII boxes, find the fewest distinct courses needed to complete any three of them.
Level

Medium4 of 10

Topics
Brute force, Hash map, String
Solved
No attempts yet

Problem

The Department of Computer Engineering has provided several micromasters, each with a curriculum. A student who completes all the courses of a micromaster receives that micromaster's certificate. A course may appear in the curriculum of several micromasters. Soroush only cares about earning a certificate, not which type it is. He wants to earn 33 micromaster certificates while taking the minimum possible number of courses. The curriculums are posted on a bulletin board. Help Soroush reach his goal using these curriculums.

Input

The input is a bulletin board of at most 400400 rows and 400400 columns. Each micromaster curriculum is enclosed in a rectangular box. The board border and the curriculum boxes are drawn with + for corners, - for horizontal sides, and | for vertical sides. The curriculum boxes do not share any characters, and each box has its own border. Each line inside a box contains at most one course name. Course names consist of letters, digits, and spaces. Course names are not case-sensitive, and spaces are ignored. For example, General math1 and generalMath 1 are the same course. There are at most 5050 curriculum boxes, and each box contains at most 3030 courses. The board has at least 33 boxes, and each box contains at least 11 course.

Output

Print a single line containing the minimum number of courses Soroush must take to earn at least 33 certificates.

Examples1

  1. Example 1

    Input
    +-------------------------------------------------+
    |  +-------------------+                          |
    |  |Algorithm Design   |   +-------------------+  |
    |  |  Programming      |   |PROGRAMMING        |  |
    |  |Discrete Structures|   |   Web Prgramming  |  |
    |  |   Data Structures |   |                   |  |
    |  +-------------------+   | DatabaseDesign    |  |
    |                          |Software Test      |  |
    |     +--------------+     |     Patterns      |  |
    |     |    Python    |     +-------------------+  |
    |     +--------------+                            |
    |          +------------------------+             |
    |          |Programming             |             |
    |          |          AI            |             |
    |          |    Algorithm     design|             |
    |          |Database Design         |             |
    |          +------------------------+             |
    +-------------------------------------------------+
    
    Expected output
    7