Modified Knapsack

Problem Statement

Modified Knapsack Problem Description You will be given N elements, each consisting of three numbers: type , weight , and value . You will also be given a value K. You have to select a few elements such that the following properties hold: You cannot pick more than one element of the same type. The total weight of the selected elements has to be less than or equal to K. The total value of the selected elements should be as large as possible. You have to output the maximized total value of the selected elements. Input Format The first line will contain an integer N . Each of the next N lines will contain three integers, representing the type , weight , and value of an element. The last line will contain an integer K . Output Format For each case, print the desired result. Constraints 1 ≤ N, type, weight, value, K ≤ 5 * 10 3 Sample 1 Input 6 1 3 13 5 1 10 2 2 1 1 4 9 4 5 11 1 5 9 6 Output 24 Explanation By taking the first three elements from the input list, we achieve the maximum p