该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Background

Muxue the youth has a bracket forest consisting of n bracket trees. He wants to select a subset from them and connect these trees to form a large valid bracket sequence.

Problem Description

Muxue has a bracket forest consisting of n bracket trees. Each bracket tree is a valid bracket sequence.

Muxue wants to select a non-empty subset from these trees and connect them in any order to form a large valid bracket sequence. When connecting, he can only append the end of one tree to the beginning of another tree, and cannot change the internal order within any tree.

Please determine whether Muxue can form a valid bracket sequence by selecting some trees and connecting them. If yes, output the minimum number of connections required (i.e., the number of selected trees minus 1).

Note: n ≤ 20 because the problem is relatively complex.

Input Format

First line: an integer n (1 ≤ n ≤ 20)
Next n lines: each line contains a string sᵢ, representing a bracket tree (1 ≤ |sᵢ| ≤ 1000, and each sᵢ is a valid bracket sequence)

Output Format

If it's possible to form a valid bracket sequence, output the minimum number of connections; otherwise output -1.

Sample Input and Output #1

Input #1

3
(())
()
()

Output #1

1

Explanation/Notes

Explanation for Sample 1: You can select () and () to connect into ()(), requiring 1 connection.

This problem uses Subtask bundled testing