import java.util.Arrays; import java.util.Scanner; public class TwoBamboo { /* メモ化用Map */ private static int[][] calculatedArray; /* 2本の竹のうち短い方の竹を対象にしてナップサック問題として考える。 */ public static void main(String[] args) { Scanner cin = new Scanner(System.in); int d = cin.nextInt(); int[][][] allQuestions = new int[d][2][]; for (int i = 0; i < d; i++) { /* 2本の竹情報 */ allQuestions[i][0] = new int[2]; allQuestions[i][0][0] = cin.nextInt(); allQuestions[i][0][1] = cin.nextInt(); /* 要求数 */ int requestsNum = cin.nextInt(); /* 要求情報 */ allQuestions[i][1] = new int[requestsNum]; for (int j = 0; j < requestsNum; j++) { allQuestions[i][1][j] = cin.nextInt(); } } for (int[][] question : allQuestions) { System.out.println(answer(question[0], question[1])); } } /* 各データセット単位で解く */ private static int answer(int[] bamboo, int[] requests) { /* 2本の竹の総和に対し、要求された長さを小さい順に足していく。要求された長さの和が2本の竹の総和を越えたら、以降の要求には絶対に応えられないので無視する。また、長いほうの竹を越える要求も満たせないので無視する */ Arrays.sort(requests); Arrays.sort(bamboo); calculatedArray = new int[requests.length][bamboo[0] + 1]; return getNum(0, bamboo[0], bamboo[1], requests); } private static int getNum(int currentIndex, int shortBamboo, int longBamboo, int[] requests) { /* 要求されるのは長さのみで重みはないので、要求を小さい順にソートしたとき、R(n)の要求に応えずにR(n+1)の要求に応えたほうがよい、というケースはない。なので、必ずどちらかの竹から切リ出して次の要求を処理する */ if (calculatedArray[currentIndex][shortBamboo] != 0) { /* 計算済み */ return calculatedArray[currentIndex][shortBamboo]; } int shortResult = 0; if (requests[currentIndex] <= shortBamboo) { shortResult++; if (currentIndex + 1 < requests.length) { shortResult += getNum(currentIndex + 1, shortBamboo - requests[currentIndex], longBamboo, requests); } } int longResult = 0; if (requests[currentIndex] <= longBamboo) { longResult++; if (currentIndex + 1 < requests.length) { longResult += getNum(currentIndex + 1, shortBamboo, longBamboo - requests[currentIndex], requests); } } int result = shortResult > longResult ? shortResult : longResult; calculatedArray[currentIndex][shortBamboo] = result; return result; } }