젤리 맛 (jelly)

Amy는 젤리를 매우 좋아하며, 디저트로 먹을 젤리를 사고 싶어 합니다. 젤리 맛은 총 $n$가지이며, $0$부터 $n-1$까지 번호가 매겨져 있습니다. 상점 A에서는 $i$번 맛 젤리 한 개를 $a[i]$달러에 판매하고, 상점 B에서는 한 개를 $b[i]$달러에 판매합니다. Amy는 상점 A에서 최대 $x$달러, 상점 B에서 최대 $y$달러를 쓸 수 있습니다.

Amy가 구매할 수 있는 서로 다른 젤리 맛의 최대 개수를 구하세요.

구현 세부사항

다음 프로시저를 구현해야 합니다.

int find_maximum_unique(int x, int y, int[] a, int[] b)

• $x$: 상점 A에서 쓸 수 있는 금액입니다.
• $y$: 상점 B에서 쓸 수 있는 금액입니다.
• $a$: 길이가 $n$인 배열로, 상점 A에서 각 젤리의 가격을 담고 있습니다.
• $b$: 길이가 $n$인 배열로, 상점 B에서 각 젤리의 가격을 담고 있습니다.
• 이 프로시저는 정확히 한 번 호출됩니다.
• 이 프로시저는 Amy가 구매할 수 있는 서로 다른 젤리 맛의 최대 개수를 반환해야 합니다.

예제

예제 1

다음 호출을 살펴봅시다.

find_maximum_unique(2, 3, [2, 1, 4], [2, 3, 2])

이는 Amy가 상점 A에서 최대 $2$달러, 상점 B에서 최대 $3$달러를 쓸 수 있으며, 가격은 다음과 같다는 뜻입니다.

• 젤리 $0$은 상점 A와 B 모두에서 $2$달러입니다.
• 젤리 $1$은 상점 A에서 $1$달러, 상점 B에서 $3$달러입니다.
• 젤리 $2$는 상점 A에서 $4$달러, 상점 B에서 $2$달러입니다.

Amy가 구매할 수 있는 서로 다른 맛의 최대 개수는 $2$입니다. 상점 A에서 젤리 $0$을 사고 상점 B에서 젤리 $2$를 각각 $2$달러에 사면 됩니다.

따라서 프로시저는 $2$를 반환해야 합니다.

예제 2

다음 호출을 살펴봅시다.

find_maximum_unique(6, 12, [5, 1, 5, 6, 3], [3, 5, 4, 6, 7])

이 경우 Amy가 구매할 수 있는 서로 다른 맛의 최대 개수는 $4$입니다. 상점 A에서 젤리 $1$과 $2$를 $1+5=6$달러에 구매하고, 상점 B에서 젤리 $0$과 $4$를 $3+7=10$달러에 구매하면 됩니다.

따라서 프로시저는 $4$를 반환해야 합니다.

제약 조건

• $1 \leq n \leq 2000$
• $0 \leq x, y \leq 10\;000$
• $0 \leq a[i], b[i] \leq 10\;000$ (모든 $0 \leq i \leq n-1$에 대해)

서브태스크

1. (11점) $x, y \leq 500$, $n \leq 12$
2. (24점) $x, y \leq 500$, $n \leq 200$
3. (9점) $y = 0$
4. (10점) $b[i]=b[j]$ (모든 $0 \leq i, j \leq n-1$에 대해)
5. (14점) $a[i]=b[i]$ (모든 $0 \leq i \leq n-1$에 대해)
6. (32점) 추가 제약 조건이 없습니다.

샘플 그레이더는 다음 형식으로 입력을 읽습니다.

• $1$번째 줄: $\;\;n\;\;x\;\;y$
• $2 + i$번째 줄 ($0 \leq i \leq n - 1$): $\;\;a[i]\;\;b[i]$

샘플 그레이더는 다음 형식으로 답을 출력합니다.

• $1$번째 줄: find_maximum_unique의 반환값.