NCEA Scholarship 2025 Digital Technologies Q3 (Sample)

San Holo and his friend Bew Chaka need your help again. They’ve just dropped out of hyperdrive in the Gollius System and there are several trade stations that they can go to. The problem is, they want to maximise the amount of profit while keeping their cargo weight less than or equal to the maximum. Your task is to quickly work out the maximum amount of profit from any combination of trades at a particular trade station. The trade items cannot be split up, and each item can only be included once. You must evaluate the maximum profit that can be made from trading at the given station from the supplied data.

Input

The first line of input is two integers, $N$ and $M$. $N$ is the number of possible trade routes that will follow, and $M$ is the maximum cargo space left on the ship. There then follows $N$ lines, each line containing an item’s weight $W$ and the profit $P$ that it will generate when sold back at base.

Constraints

$1 \le N,M \le 1000$

Output

Output will be a single line containing one integer value for the maximum profit that you can achieve at this station.

This question is taken with permission from Scholarship Digital Technologies 93604 (Sample assessment 2025). However, subtasks and test data (with the exception of the sample data) are created independently by the NZOI. Your result is no indication of exam performance. These questions are unlikely to be sufficient preparation for the exam. NZQA owns the copyright in the examination material reproduced, and has consented to its reproduction, but takes no responsibility for its accuracy or fitness for purpose. The performance standard by which the scholarship assessments are assessed, varies significantly from the NZOI grading and selection process, and success in the NZOI selection process does not guarantee gaining a Scholarship in Digital Technologies. This question cannot be reproduced by any means without the prior permission of NZQA.

Submission

For our site, go to the submit tab to upload your solution.

Please note: If you're using Python, submit your solution with Python 3.6 (PyPy 7.3). Python 3.8 will be too slow.

Additional Constraints

• $1 \le W,P \le 1,000,000$.

Subtasks

• Subtask 1 (20%): $N,M \le 10$. Boundary cases.
• Subtask 2 (30%): $N,M \le 50$.
• Subtask 3 (20%): $N,M \le 500$.
• Subtask 4 (25%): $N,M \le 1,000$.
• Subtask 5 (5%): $N,M \le 8,000$. This subtask is extra for experts and exceeds the bounds given in the question.