Description

The owner of XX Hotel wants to become the "Hotel King." With this goal, the first step is to make the hotel more user-friendly. Many guests have their preferences for room color tones, sunlight, and favorite dishes. However, the hotel has only $p$ rooms, and there are only $q$ different dishes each day. Each room can accommodate only one guest, and each dish can be served to only one guest.

One day, $n$ guests arrived. Each guest stated which rooms they like and which dishes they like. Unfortunately, it may be impossible to satisfy all guests (a guest is satisfied if they both live in a liked room and eat a liked dish).

How should we assign rooms and dishes to maximize the number of satisfied guests?

Input Format

The first line contains three integers, representing $n, p, q$.

Then follow $n$ lines, each containing $p$ integers, each being $0$ or $1$. On the $i$-th line, the $j$-th number indicates whether the $i$-th person likes the $j$-th room ($1$ means like, $0$ means do not like).

Then follow $n$ lines, each containing $q$ integers, each being $0$ or $1$. On the $i$-th line, the $j$-th number indicates whether the $i$-th person likes the $j$-th dish ($1$ means like, $0$ means do not like).

Output Format

Output the maximum number of satisfied guests.

2 2 2
1 0
1 0
1 1
1 1

1

Hint

Constraints

For all test points, $1 \leq n, p, q \leq 100$.

Translated by ChatGPT 5