There is a scientific competition held every year in which students participate in the form of teams, the team that solves all the problems wins. We know that every student has power Pi in a subject Si.
It is given that quiz questions will demand powers of at least Qpj in subject j (where j is from 1 to k). If there are two students with power X and Y in subject Z, the power of the team in that subject will be X + Y.
You have N students and want to choose from them a team that can solve all the problems of the competition and be composed of as few students as possible. It is mandatory that you choose a successive subgroup while selecting a team.
Your task is to find the smallest number of students in the team to be able to win. If it is not possible to determine the answer print -1.
Function Description
Complete the CalcMin function in the editor below. It has the following parameter(s):
| Name | Type | Description |
|---|---|---|
| K | INTEGER | Number of subjects. |
| N | INTEGER | Number of students. |
| Qp | INTEGER ARRAY | The power required to solve the problems of each subject. |
| S | INTEGER ARRAY | Favorite subject for each student. |
| P | INTEGER ARRAY | The power of the student in his subject. |
| Return. | The function must return an INTEGER denoting the smallest number of students in the team to be able to win. |
Constraints
1. 1 ≤ K ≤ 10^3
2. 1 ≤ N ≤ 10^6
3. 1 ≤ Qp[i] ≤ 10^5
4. 1 ≤ S[i] ≤ K
5. 1 ≤ P[i] ≤ 10^5
Input format for debugging
1. The first line contains an integer, K, denoting the number of elements in Qp.
2. The next line contains an integer, N, denoting the number of elements in S.
3. Each line i of the K subsequent lines (where 0 ≤ i < K) contains an integer describing Qpi.
4. Each line i of the N subsequent lines (where 0 ≤ i < N) contains an integer describing Si.
5. Each line i of the N subsequent lines (where 0 ≤ i < N) contains an integer describing Pi.
Sample Testcases
| Input | Output | Output Description |
| 1 3 5 1 1 1 3 1 3 | 3 | Here we will take all the students so that the team can solve all the problems. |
| 2 4 4 2 1 2 1 1 2 2 3 5 | 3 | Here we will take the first three students. |
| 2 4 4 4 1 2 2 1 5 5 5 5 | 2 | Here we will take the first two students. |
Skill Covered
- Fullstack
- MEAN Stack
Assessing
- Fundamentals
Question Type
- Project
