All submissions for this problem are available.
We have ‘N’ items each of type Tp[i] where Tp[i] is from 1 to k.
Each item has a profit P[i] associated with it. We also have an array M containing 'k' elements : M , M .... , M[k]. We have to select some items from all N items such that :
- For two selected items 'i' and 'j' => P[i] != P[j]
- Number of selected items from a given type ‘j’ is <= M[j]
- Sum of profits of selected items is maximized
Note that two items having same type may have different profit values.
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows."
- First line of each test case contains N and k
- The next N lines contain 2 integers. The i'th of the next n lines contains 2 integers Tp[i] and P[i]
- Last line contains k integers M,M .... M[k]
- For each test case, output a single line containing the maximum profit we can get from the selected items
- 1 ≤ T ≤ 5
- 1 ≤ N ≤ 100
- 1 ≤ M,....M[k] ≤ N
- 1 ≤ k, P,P,.....P[N] ≤ 1000
- 1 ≤ Tp[i] ≤ k
Input: 1 3 2 1 2 1 3 2 3 1 1 Output: 5
Example case 1.We have 2 types of items. From each type, only 1 item can be selected. As profits of 2 selected items should not be same, we will select the first and the third item
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions