Your given a a list of people and their skillsset. We need to form a team out of these people with as many people as we want. The only condition is each of the skills has a maximum allowed amount in the team formed. i.e Sum of ith skill from all people in the team should be <= Maximum allowed value of the ith skill.

Input starts with 3 integers N S M i.e number of people , total number of skills and total number of edges . Next M lines follow with 3 integers A B C meaning person A has skill B with total amount C. This is followed by S lines with 2 integers X Y where X = skill number and Y = maximum amount of skill X that is allowed to be in the team.

Example Input:

4 2 7

1 1 1

2 1 1

2 2 1

3 1 1

3 2 1

4 2 1

5 2 1

1 2

2 2

Output:

3

In the above example there are multiple options to build a team. We can choose 2,3 to form the team and in this case the total skill = 2 and 2. Person 2 has skills 1 and 2, and person 3 also has skills 1 and 2. We cannot add any more elements since then we will exceed the total skills level allowed in a team. The subset = 1,4,5 or 1,2,5 or 1,3,5 is optimal because the skills level is not breached.

I tried to formulate a maxflow graph but the issue is if a node is chosen then all the edges from it have to be chosen so this wasn't boiling to a network flow graph. I wanted to know if this is a NP-Hard problem and how do we prove that indeed a problem is Np-hard.