전선 비용

네트워크를 새로 구축하려는데 전선이 모자란다. 부족한 길이는 0미터에서 100미터 사이의 어떤 값이든 될 수 있다.

가게에는 길이도 가격도 제각각인 전선 조각이 여러 개 있고, 조각 길이의 합은 정확히 100미터다. 가격이 같은 조각이 둘 이상 있을 수 있고, 길이도 마찬가지다. 길이와 가격 사이에는 아무 관계가 없어서 가장 짧은 조각이 가장 비쌀 수도 있다.

전선은 잘라서 짧게 만들 수 있고, 두 조각을 이어 붙여 더 길게 만들 수도 있다. 이어 붙일 때 생기는 손실은 무시한다.

이 가게에는 특이한 할인이 있다. 조각을 하나 사면 그 조각의 가격보다 엄격히 싼 조각은 모두 공짜로 가져갈 수 있다. 가격이 같은 조각은 공짜가 아니라서, 필요하면 하나씩 따로 사야 한다.

필요한 길이 이상을 확보하는 데 드는 최소 비용을 구하라.

첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 20$)가 주어진다.

각 테스트 케이스의 첫 줄에는 가게에 있는 전선 조각의 개수 $N$ ($0 < N < 100$)이 주어진다. 둘째 줄에는 $1$번부터 $N$번 조각의 가격이 공백 하나로 구분되어 주어진다. 각 가격은 $500$보다 작은 양의 정수다. 셋째 줄에는 같은 순서로 각 조각의 길이가 공백 하나로 구분되어 주어진다. 각 길이는 양의 정수이고, 길이의 합은 $100$이다. 넷째 줄에는 필요한 전선의 길이가 주어진다. 이 값은 $100$보다 작은 양의 정수다.

각 테스트 케이스마다 필요한 길이 이상의 전선을 얻는 데 드는 최소 비용을 한 줄에 정수 하나로 출력한다.