← 返回 microsoft 的题目列表Max Investors Met Within K Days Given Availability Lists
类型：online_judge
Problem: Max Investors Met Within K Days Given Availability Lists (DP)
A founder wants to meet investors over the coming days.
There are n investors (0..n-1)
Each investor i provides a list avail[i] of integer days they are available
The founder can meet at most one investor per day
Each investor can be met at most once
You can schedule meetings on at most k distinct days (i.e., at most k meetings)
Compute the maximum number of investors the founder can meet.
Input (stdin)
First line: n k
Next n lines: an integer m followed by m available days
Output (stdout)
One integer: maximum investors that can be met
Constraints
1 <= n <= 2000
1 <= k <= 2000
Total m across investors <= 2e5
Days are integers in [0, 1e9]
Examples
See the 5 test cases in the Chinese version.
Example
Input
3 2
2 1 2
2 2 3
1 1
Output
2