Z-tube Cat recommends you play Ballance. In the game, players take control of a ball with variable material properties, guiding it through a vast and intricate maze of road surfaces and mechanisms. Along the way, you must avoid traps, activate mechanisms, and solve puzzles to ultimately reach the finish line.
Ballance has $$$3$$$ material types (paper ball, wooden ball, stone ball). During gameplay, the ball must pass through $$$n$$$ mechanisms, each of which can only be passed by balls of specific material types. Initially, you must spend $$$1$$$ unit to select one material type for the ball. Before passing each mechanism, you may spend $$$1$$$ unit to switch the ball to another material type or choose to keep the current material at no cost.
You may freely arrange the order of passage through the mechanisms. Determine the minimum cost required for the ball to pass through all $$$n$$$ mechanisms.
The first line contains an integer $$$n (1 \le n \le 100)$$$, the number of mechanisms.
Each of the next $$$n$$$ lines contains three integers $$$a_{i,1}, a_{i,2}, a_{i,3} \in \{0, 1\}$$$.
For the $$$i$$$-th mechanism, $$$a_{i,j} = 1$$$ indicates that the $$$j$$$-th ball type is allowed to pass, while $$$a_{i,j} = 0$$$ indicates it is prohibited.
It is guaranteed that for each mechanism, not all $$$a_{i,j}$$$ are zero.
One line containing an integer, representing the minimum cost required for the ball to pass through these $$$n$$$ mechanisms, achieved by rationally arranging the sequence of passage and the material costs.
5 1 0 0 1 0 1 0 1 0 1 0 1 0 0 1
3
