#K41952. Maximum Non-Identical Projects Allocation

    ID: 26979 Type: Default 1000ms 256MiB

Maximum Non-Identical Projects Allocation

Maximum Non-Identical Projects Allocation

You are given (n) projects and (k) available slots. Each project requires a specified number of tables and each slot has a table capacity. Your task is to determine the maximum number of projects that can be set up such that each project is assigned to a unique slot with sufficient table capacity.

Formally, you are given two sequences: (T = [t_1, t_2, \dots, t_n]) representing the tables required by each project and (S = [s_1, s_2, \dots, s_k]) representing the capacities of the slots. A project (i) can be assigned to slot (j) if (t_i \le s_j). Each slot can be used for at most one project. The solution involves a greedy matching procedure after sorting both sequences.

inputFormat

The input is read from standard input (stdin) in the following format:

(n) (k)
(t_1) (t_2) ... (t_n)
(s_1) (s_2) ... (s_k)

Where:
- (n) is the number of projects.
- (k) is the number of slots.
- The next line contains (n) integers describing the tables required for each project.
- The following line contains (k) integers describing the table capacities of the slots.

outputFormat

Output a single integer to standard output (stdout) representing the maximum number of projects that can successfully be assigned a slot satisfying the table capacity constraint.## sample

5 3
2 3 5 1 4
5 5 3
3