0/1 Knapsack

Given N items with values and weights and a bag capacity W, choose a subset of items to maximise total value without exceeding the capacity. Each item may be used at most once.

Input Format

The first line contains an integer N. The second line contains N space-separated integers — the values. The third line contains N space-separated integers — the weights. The fourth line contains an integer W, the capacity.

Output Format

Print the maximum total value.