Wiring Cost

You are setting up a network and you are short on wire. The missing length can be any value from 0 to 100 meters.

A nearby store sells wire in pieces of assorted lengths and prices, and the lengths of all the pieces add up to exactly 100 meters. Several pieces can share the same price, and several can share the same length. Length and price are unrelated, so the shortest piece can be the most expensive one.

You can cut a piece to make it shorter, and you can join two pieces into a longer one. Wire lost while joining is ignored.

The store runs an unusual discount. Once you buy a piece, every piece priced strictly lower than it is yours for free. Pieces that carry the same price are not free, so you pay for each one of those you take.

Find the minimum cost of ending up with at least the length of wire you need.

The first line contains the number of test cases $T$ ($1 \le T \le 20$).

The first line of each test case contains $N$ ($0 < N < 100$), the number of wire pieces in the store. The second line contains the prices of pieces $1$ through $N$, separated by single spaces. Each price is a positive integer smaller than $500$. The third line contains the lengths of the same pieces in the same order, separated by single spaces. Each length is a positive integer and the lengths add up to $100$. The fourth line contains the required length of wire, a positive integer smaller than $100$.

For each test case, print one line with a single integer, the minimum cost of obtaining at least the required length of wire.