navi-and-his-friend
Source: hackerearth
Difficulty: EASY

Navi is a famous shopkeeper in his locality. He gives discounts to his regular customers. Some new rules have been made due to which he is in trouble. According to the new rules, any shopkeeper can sale his items to only one customer in a day. But every customer has some issues like the total money they have or the total weight they can handle at a time or number of items they are interested in. Navi’s friend has decided to help Navi and he promised him that he will purchase items from his shop daily and try to maximize his sale in terms of total price with satisfying the count of items and weight of the items . He will give his requirements as Wmax (maximum weight he can carry) and C (maximum count of the items he can carry). Now Navi is interested in knowing the total price of the items he can sell.

Input
First line of input will contain D (total number of days). Then for each day first line will contain N (Number of items) . Next each N lines will contains two integers P (price of ith item on that day) and W(weight of ith item on that day) separated by a space. Last line for the input of the particular day will contain Wmax  and C separated by a space.

Output
For each day output “For Day #day_number:” then in next line print the maximum total price. If his friend is not able to purchase any of the item then print -1.
Constraints
1 < = D < = 10

1 < = N < = 16

1 < = C < = 20

1 < =  Pi , Wi , Wmax < = 10^9

SAMPLE INPUT
1
3
10 20
20 30
30 40
50 2

SAMPLE OUTPUT
For Day #1:
30

Explanation

He will buy first and second item.


import math


def solve(indx, sums, prev, curr):
	global noOfItem, cnts, wtMax, price, weight
	if indx == noOfItem or curr == cnts or sums == wtMax:
		return prev
	ans1 = solve(indx + 1, sums, prev, curr)
	ans2 = 0
	if (sums + weight[indx]) <= wtMax:
		ans2 = solve(indx + 1, sums + weight[indx], prev + price[indx], curr + 1)
	return max(ans1, ans2)


noOfDays = eval(input())
for d in range(noOfDays):
	noOfItem = eval(input())
	price = []
	weight = []
	for i in range(noOfItem):
		a, b = list(map(int, input().split()))
		price.append(a)
		weight.append(b)
	wtMax, cnts = list(map(int, input().split()))
	ans = solve(0, 0, 0, 0)
	if ans > 0:
		answ = ans
	else:
		answ = - 1

	print("For Day #{}:".format(d + 1))
	print(answ)