Jelly Flavours (jelly)

Amy is a big fan of jelly, and wishes to buy some for dessert. There are a total of n flavours of jelly, numbered 0 to n − 1. Store A sells jelly of flavour i for a[i] dollars a piece, whereas Store B sells it for b[i] dollars a piece. Amy can spend up to x dollars in Store A and up to y dollars in Store B.

Help Amy find the maximum number of unique flavours of jelly she can purchase.

Implementation details

You should implement the following procedure:

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

• x: amount of money that can be spent in Store A.
• y: amount of money that can be spent in Store B.
• a: an array of length n, containing the cost of each jelly in Store A.
• b: an array of length n, containing the cost of each jelly in Store B.
• This procedure will be called exactly once.
• The procedure should return the maximum number of unique flavours of jelly Amy can purchase.

Example

Example 1

Consider the following call:

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

This means that Amy can spend up to 2 dollars in Store A and 3 dollars in Store B, and the prices are as follows:
- Jelly 0 costs 2 dollars in both Store A and B,
- Jelly 1 costs 1 dollar in Store A and 3 dollars in Store B,
- Jelly 2 costs 4 dollars in Store A and 2 dollars in Store B.

The maximum number of unique flavours Amy can purchase is 2. This can be done by buying jelly 0 from Store A and jelly 2 from Store B for 2 dollars each.

Therefore, the procedure should return 2.

Example 2

Consider the following call:

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

In this case, the maximum number of unique flavours Amy can purchase is 4. This can be done by purchasing jellies 1 and 2 from Store A, costing 1 + 5 = 6 dollars, as well as jellies 0 and 4 from Store B, costing 3 + 7 = 10 dollars.

Therefore, the procedure should return 4.

Constraints

• $1 \le n \le 2000$
• $0 \le x, y \le 10\,000$
• $0 \le a[i], b[i] \le 10\,000$ (for all $0 \le i \le n - 1$)

Sample grader

The sample grader reads the input in the following format:

• line 1: n x y
• line 2 + i (0 ≤ i ≤ n − 1): a[i] b[i]

The sample grader prints your answers in the following format:

• line 1: the return value of find_maximum_unique.

You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution, then provide a complete implementation in C++17. You should correctly implement the routine(s) described in Implementation Details, without reading or writing anything directly from stdin or to stdout, as input and output are passed through the implemented routines. Assume your code will be run on the OFFICIAL grader, and do not add a main, a sample grader, or any other functionality unless it has been explicitly requested.
Put your final solution within a single code block: cpp <your code here>

Problem statement (Jelly Flavours)

(jelly)

Amy is a big fan of jelly, and wishes to buy some for dessert. There are a total of n flavours of jelly, numbered 0 to n − 1. Store A sells jelly of flavour i for a[i] dollars a piece, whereas Store B sells it for b[i] dollars a piece. Amy can spend up to x dollars in Store A and up to y dollars in Store B.

Help Amy find the maximum number of unique flavours of jelly she can purchase.

Implementation details

You should implement the following procedure:

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

• x: amount of money that can be spent in Store A.
• y: amount of money that can be spent in Store B.
• a: an array of length n, containing the cost of each jelly in Store A.
• b: an array of length n, containing the cost of each jelly in Store B.
• This procedure will be called exactly once.
• The procedure should return the maximum number of unique flavours of jelly Amy can purchase.

Example

Example 1

Consider the following call:

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

This means that Amy can spend up to 2 dollars in Store A and 3 dollars in Store B, and the prices are as follows:
- Jelly 0 costs 2 dollars in both Store A and B,
- Jelly 1 costs 1 dollar in Store A and 3 dollars in Store B,
- Jelly 2 costs 4 dollars in Store A and 2 dollars in Store B.

The maximum number of unique flavours Amy can purchase is 2. This can be done by buying jelly 0 from Store A and jelly 2 from Store B for 2 dollars each.

Therefore, the procedure should return 2.

Example 2

Consider the following call:

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

In this case, the maximum number of unique flavours Amy can purchase is 4. This can be done by purchasing jellies 1 and 2 from Store A, costing 1 + 5 = 6 dollars, as well as jellies 0 and 4 from Store B, costing 3 + 7 = 10 dollars.

Therefore, the procedure should return 4.

Constraints

• $1 \le n \le 2000$
• $0 \le x, y \le 10\,000$
• $0 \le a[i], b[i] \le 10\,000$ (for all $0 \le i \le n - 1$)

Sample grader

The sample grader reads the input in the following format:

• line 1: n x y
• line 2 + i (0 ≤ i ≤ n − 1): a[i] b[i]

The sample grader prints your answers in the following format:

• line 1: the return value of find_maximum_unique.

Execution limits

Your solution will have 1.0 second(s) execution time and 2048 MB memory limit to solve each test case.

Starting code

Here's your starting code with some skeleton/placeholder functionality:

#include "jelly.h"
#include <vector>

int find_maximum_unique(int x, int y, std::vector<int> a, std::vector<int> b) {
    int n = a.size();
    return n;
}

参考函数签名

#include "jelly.h"
#include <vector>

int find_maximum_unique(int x, int y, std::vector<int> a, std::vector<int> b) {
    int n = a.size();
    return n;
}

请在 submission.cpp 中实现该函数（可 #include "problem.h" 获取题目提供的声明）。判题时你的代码会与题目提供的 grader 一起编译链接。

本题是函数题，由 grader 调用你实现的函数。

由 grader 打印判定结果，无需自行读写 stdin/stdout。

include "jelly.h"

include <vector>

int find_maximum_unique(int x, int y, std::vector<int> a, std::vector<int> b) {
int n = a.size();
return n;
}