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.

SPOJ Problem POWPOW Here is my code....... http://ideone.com/t29P3j

mod=1000000003 ,phi_mod=500000003

I have done it as follows--- --X congruent exp mod 500000003 ---X congruent 1 mod 2 ---solve for X using CRT.... ---X is (2nCn %(mod-1)) --then do ans1=powmod(X^b,mod-1) ----ans2=powmod(a^ans1,mod) print ans2 It is giving WA

This question is from amritapuri prelimnary for regional qualification...... Obviously the contest is over now..........

Given a sequence S of '0' and '1' of length N, a subsequence of S is obtained by omitting some elements of S without changing the order of the remaining elements of S.

Given a subarray of a sequence S starting from some position 'a' and ending at some position 'b' (1 <= a <= b <= N), both inclusive, denoted by S(a,b), you have report the length of longest non-decreasing subsequence of S(a,b). By non-decreasing, we mean that a '0' never appears after a '1' in the subsequence.

Input (STDIN): The first line contains T, the number of test cases. Then T test case follow, each test case being in the following format. The first line contains N, the length of sequence S. The next line contains a string of 0's and 1's of length exactly N. The next line contains Q, which means that you have to answer Q queries. The next Q lines contain a pair of integers a,b (1 <= a <= b <= N), meaning that you have to report the length of longest non decreasing subsequence of S(a,b). There is no blank line between test cases.

Output (STDOUT): Output Q lines per test case, which is the answer for each query. Do not print a blank line between test cases. Constraints:

1 <= T <= 10 1 <= N <= 100,000 1 <= Q <= 100,000 Sample Input:

1 13 0011101001110 6 1 13 4 13 1 9 6 9 3 3 6 10

Sample Output:

9 6 6 3 1 4

Plz tell me the algorithm..........