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 W_max (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 W_max and C separated by a space.

Output

Constraints

1 < = N < = 16

1 < = C < = 20

1 < = P_i , W_i , W_max < = 10⁹