[Solution] Schedule Management solution codeforces

Schedule Management solution codeforces – There are 𝑛n workers and 𝑚m tasks. The workers are numbered from 11 to 𝑛n. Each task 𝑖i has a value 𝑎𝑖ai — the index of worker who is proficient in this task.

Table of Contents

[Solution] Schedule Management solution codeforces

Every task should have a worker assigned to it. If a worker is proficient in the task, they complete it in 11 hour. Otherwise, it takes them 22 hours.

The workers work in parallel, independently of each other. Each worker can only work on one task at once.

Assign the workers to all tasks in such a way that the tasks are completed as early as possible. The work starts at time 00. What’s the minimum time all tasks can be completed by?

Input

The first line contains a single integer 𝑡t (1𝑡1041≤t≤104) — the number of testcases.

The first line of each testcase contains two integers 𝑛n and 𝑚m (1𝑛𝑚21051≤n≤m≤2⋅105) — the number of workers and the number of tasks.

The second line contains 𝑚m integers 𝑎1,𝑎2,,𝑎𝑚a1,a2,…,am (1𝑎𝑖𝑛1≤ai≤n) — the index of the worker proficient in the 𝑖i-th task.

The sum of 𝑚m over all testcases doesn’t exceed 21052⋅105.

[Solution] Schedule Management solution codeforces

For each testcase, print a single integer — the minimum time all tasks can be completed by.

Example
input

Copy
4
2 4
1 2 1 2
2 4
1 1 1 1
5 5
5 1 3 2 4
1 1
1
output

Copy
2
3
1
1

[Solution] Schedule Management solution codeforces

In the first testcase, the first worker works on tasks 11 and 33, and the second worker works on tasks 22 and 44. Since they both are proficient in the corresponding tasks, they take 11 hour on each. Both of them complete 22 tasks in 22 hours. Thus, all tasks are completed by 22 hours.

In the second testcase, it’s optimal to assign the first worker to tasks 1,21,2 and 33 and the second worker to task 44. The first worker spends 33 hours, the second worker spends 22 hours (since they are not proficient in the taken task).

In the third example, each worker can be assigned to the task they are proficient at. Thus, each of them complete their task in 11 hour.

For Solution

Click Here

Leave a Comment