Chrome
InterviewTime limit1sMemory limit512 MB
Given N tabs each with CPU and memory usage plus a priority, choose a subset whose total CPU and memory reach the targets M and K while minimizing the sum of priorities.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Array, Implementation, Brute force
- Solved
- No attempts yet
Problem
Shinyoung is playing a game, and the severe lag is making him angry.
To play comfortably, he needs to secure a certain amount of CPU usage and memory.
Shinyoung usually keeps a lot of Chrome incognito tabs open, and he plans to close these Chrome tabs to free up resources.
A Chrome tab is described by its CPU usage, memory usage, and priority.
Closing a tab frees up resources equal to the tab's CPU and memory usage.
Each tab has a priority, which indicates how important it is, and Shinyoung wants the sum of the priorities of the closed tabs to be as small as possible.
Find the minimum possible sum of priorities when closing Chrome tabs to secure CPU and memory at or above the targets.
Input
The first line gives the values of N, M, K. (N ≤ 100, M ≤ 1,000, K ≤ 100,000)
N is the total number of Chrome tabs. M is the target CPU usage. K is the target memory amount.
The next N lines give the information of each Chrome tab as follows.
cpu, memory, priority (1 ≤ cpu ≤ M, 1 ≤ memory ≤ K, 1 ≤ priority ≤ 5)
Output
Print the minimum possible sum of priorities.
If it is impossible to secure CPU and memory up to the targets, print -1.