0 Judge
Code: 0
卡邦想要組織一個商隊,幸運的是他有許多動物的朋友,她需要有可以幫忙運貨的朋友,可是他的糧草有限,每位朋友有自己的食量跟負重,可能只能帶一些朋友運貨,被選中的朋友們會一起拉一個大推車來運貨。
商隊最重要的就是商品了,卡邦找到了各式各樣商品,每個商品有自己的重量與價值,並且不能分割,由於卡邦有很多朋友與商品,不知道該如何選擇,希望你能找出卡邦最多能帶多少價值的商品。
第一行有一個數字$T \leq 10$,代表測資數。 接下來T組測資, 第一行有三個數字N,M,S,代表朋友數,商品數跟糧草量。 第二行有2 N個數字$(a_1, b_1, ..., a_n, b_n)$,$a_i$代表第i個朋友的食量($1 \leq a_i \leq 1000$),$b_i$代表第i個朋友的負重($1 \leq b_i \leq 10$)。 第三行有2 M個數字$(a_1, b_1, ..., a_n, b_n)$,$a_i$代表第i個商品的重量($1 \leq a_i \leq 1000$),$b_i$代表第i個商品的價值($1 \leq b_i \leq 1000$)。
對每筆測資輸出卡邦能帶的最大價值。
$N, M \leq 10, 1 \leq S \leq 1000$
$N \leq 100, M \leq 1000, 1 \leq S \leq 1000$