Maple Leaf Story
InterviewTime limit1sMemory limit256 MB
Bind n skills of 2n to n keys so maximum quests each needing k skills all bound can be cleared. n <= 10, m <= 100.
- Level
Hard8 of 10
- Topics
- Brute force, Combinatorics, Implementation, Bit manipulation
- Solved
- No attempts yet
Problem
Riyuna and Raga enjoy the grind that is MapleStory. MapleStory lets you set key bindings; with key bindings, you can press a key you choose to make the game cast a skill you choose.
Riyuna and Raga used to be good friends. Riyuna is level 225, while Raga is only level 202. Raga was jealous of Riyuna and tried to catch up to her Maple level. So that Riyuna could not play MapleStory, Raga broke every key on the keyboard except n of them!
But Riyuna had already sold her life to Maple, so she had to keep doing her daily quests even with the broken keys! She had to place n of the 2n skills on keys in some suitable way and somehow finish her daily quests!
The daily quests work as follows. There are m quests. Each quest requires using k skills. If a skill cannot be used, that quest is considered impossible to complete.
Riyuna wants to place skills on the n keys. In the real game you can set key bindings however you like, and you can use a skill by double-clicking even without setting a key binding, but here we assume that once key bindings are set they cannot be changed for the rest of the day, and that skills cannot be used by double-clicking. Find which skills she should place to clear as many daily quests as possible.
Input
The first line gives the number of keys n, the number of quests m, and the number of skills each quest requires k. n is at most 10, k is a positive integer at most n, and m is a positive integer at most 100.
From the second line through the m-th line, the skills each quest requires are given. Skill names are integers from 1 to 2n.
Output
On the first line, print the maximum number of quests that can be cleared with the best possible key binding.