A collector runs a private vault network with m vaults and n distinct key types, numbered 1 to n. Vault i's requirement list is a row of n values, each 0 or 1: a 1 in column j means vault i requires key type j to open. Key types the vault does not require (marked 0) are irrelevant to it — a vault opens if and only if every key type it requires is currently kept active, regardless of which other key types happen to be active as well.
The collector can afford to keep exactly numSelect of the n key types active at once. Choose which numSelect key types to keep active so as to maximize the number of vaults that open simultaneously, and report that maximum count.
Line 1: three space-separated integers m n numSelect.
Each of the next m lines contains n space-separated integers (each 0 or 1) — vault i's requirement row.
Print a single integer: the maximum number of vaults that can be opened by keeping exactly numSelect key types active.
1 <= m, n <= 120 or 11 <= numSelect <= nExample 1
Input
3 4 2 1 0 0 0 0 0 1 1 1 1 0 0
Expected
2
Explanation
Vault 1 needs only key 1, vault 2 needs keys 3 and 4, vault 3 needs keys 1 and 2. Selecting key types {1,2} opens vault 1 (needs {1}, subset of {1,2}) and vault 3 (needs {1,2}, subset of {1,2}), but not vault 2 (needs {3,4}). No other pair of key types opens both vault 2 and either of the others at once, since covering all three would require all 4 key types but the budget is only 2. The best achievable is 2 vaults.
Example 2
Input
2 3 1 1 1 1 0 0 0
Expected
1
Explanation
Vault 1 needs all three key types, but the budget allows only 1 active key type, so vault 1 can never open. Vault 2 has no requirements at all, so it is always considered open regardless of which single key type is chosen. The maximum number of vaults open is therefore 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →