Winning Team

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):

NameTypeDescription
KINTEGERNumber of subjects.
NINTEGERNumber of students.
QpINTEGER ARRAYThe power required to solve the problems of each subject.
SINTEGER ARRAYFavorite subject for each student.
PINTEGER ARRAYThe 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

InputOutputOutput Description
1 3 5 1 1 1 3 1 33Here 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 53Here we will take the first three students.
2 4 4 4 1 2 2 1 5 5 5 52Here we will take the first two students.

Skill Covered

  • Fullstack
  • MEAN Stack

Assessing

  • Fundamentals

Question Type

  • Project

Related Posts

Close Bitnami banner
Bitnami