串串：「這就是傳說中的...」
電電：「沒錯，是可以解決一切問題的神器，AC自動機。我們趕快把它拿走吧1～」
串串：「等一下！你看那個戴物臺不太對勁...」
電電的手碰觸到神器的瞬間，戴物臺發出一陣吵雜聲，隨著整個空間都開始晃動，電電迅速把手伸了回去，一切又回復了平靜。
串串：「看來這不是普通的酨物臺，這是重量感測器。如果戴物臺上的重量發生大幅變動時，感測器會感應到並觸發陷阱。」
電電：「那怎麼辦？」
串串：「沒辦法了，我們把身上的東西挑一些出來，等我們拿走神器後趁感測器還沒回復時放上去，如果我們可以讓放上去的物重和神器的重量相差不超過K，應該就不會觸發陷阱。可是這些物品中還有不少很好的寶藏，這樣丟掉實在有點可惜...」 電電：「所以是要求放上去的物品的價值總和最低嗎？既然這樣，我們就用AC自動機來解決我們的煩惱吧1～」
串串：「你在說甚麼？AC自動機是字串演算法吧。」        

輸入格式

第一行有三個數字N,W,K，表示物品的數量、神器的重量、感測器能承受的最大差值。 第二、三行各有N個數字，分別代表物品i的重量\(w_i\)與價值\(v_i\)。 \((0 \leq N,W,K,w_i,v_i \leq 2000)\)  

輸出格式

輸出最小的價值總和，如果無法讓放上去的物重和神器的重量相差不超過K則輸出-1。

範例輸入 1

5 20 1
6 20 15 8 13
100 350 50 200 120

範例輸出 1

150

範例輸入 2

3 10 15
6 9 15
90 100 120

範例輸出 2

0

範例輸入 3

5 101 0
100 50 40 20 30
100 50 40 20 30

範例輸出 3

-1

範例輸入 4

10 20 2
9 8 1 10 12 16 6 8 18 13
15 8 17 11 10 20 30 10 19 16

範例輸出 4

18

提示

子題一(40%)：\(N \leq 10\)
子題二(20%)：\(K = 0\) 
子題三(40%)：無其他限制。