Polycarp often uses his smartphone. He has already installed n applications on it.…
- User
Polycarp often uses his smartphone. He has already installed n applications on it. Application with number i takes up a_i units of memory.
Polycarp wants to free at least m units of memory (by removing some applications).
Of course, some applications are more important to Polycarp than others. He came up with the following scoring system — he assigned an integer b_i to each application:
- b_i = 1 — regular application;
- b_i = 2 — important application.
According to this rating system, his phone has b_1 + b_2 + … + b_n convenience points.
Polycarp believes that if he removes applications with numbers i_1, i_2, …, i_k, then he will free a_{i_1} + a_{i_2} + … + a_{i_k} units of memory and lose b_{i_1} + b_{i_2} + … + b_{i_k} convenience points.
For example, if n=5, m=7, a=[5, 3, 2, 1, 4], b=[2, 1, 1, 2, 1], then Polycarp can uninstall the following application sets (not all options are listed below):
- applications with numbers 1, 4 and 5. In this case, it will free a_1+a_4+a_5=10 units of memory and lose b_1+b_4+b_5=5 convenience points;
- applications with numbers 1 and 3. In this case, it will free a_1+a_3=7 units of memory and lose b_1+b_3=3 convenience points.
- applications with numbers 2 and 5. In this case, it will free a_2+a_5=7 memory units and lose b_2+b_5=2 convenience points.
Help Polycarp, choose a set of applications, such that if removing them will free at least m units of memory and lose the minimum number of convenience points, or indicate that such a set does not exist. Input
The first line contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then t test cases follow.
The first line of each test case contains two integers n and m (1 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ m ≤ 10^9) — the number of applications on Polycarp's phone and the number of memory units to be freed.
The second line of each test case contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9) — the number of memory units used by applications.
The third line of each test case contains n integers b_1, b_2, …, b_n (1 ≤ b_i ≤ 2) — the convenience points of each application.
It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5.
Output
For each test case, output on a separate line:
- -1, if there is no set of applications, removing which will free at least m units of memory;
- the minimum number of convenience points that Polycarp will lose if such a set exists.
Example
Input
5 5 7 5 3 2 1 4 2 1 1 2 1 1 3 2 1 5 10 2 3 2 3 2 1 2 1 2 1 4 10 5 1 3 4 1 2 1 2 4 5 3 2 1 2 2 1 2 1
Output
2 -1 6 4 3
Note
In the first test case, it is optimal to remove applications with numbers 2 and 5, freeing 7 units of memory. b_2+b_5=2.
In the second test case, by removing the only application, Polycarp will be able to clear only 2 of memory units out of the 3 needed.
In the third test case, it is optimal to remove applications with numbers 1, 2, 3 and 4, freeing 10 units of memory. b_1+b_2+b_3+b_4=6.
In the fourth test case, it is optimal to remove applications with numbers 1, 3 and 4, freeing 12 units of memory. b_1+b_3+b_4=4.
In the fifth test case, it is optimal to remove applications with numbers 1 and 2, freeing 5 units of memory. b_1+b_2=3.
Assistant
We are given a problem: There are n applications. Each has memory a_i (positive integer up to 1e9) and type b_i ∈ {1,2} indicating convenience points. When removing a set, you free sum of a_i and lose sum of b_i convenience points. We need to free at least m units of memory (so sum a_i >= m) while minimizing sum b_i. If not possible, output -1.
We need to handle up to 2e5 total n across test cases. m up to 1e9. So we need efficient algorithm.
Observation: Since b_i is only 1 or 2, we can think of partitioning apps into two groups: type1 and type2. We need to select some apps from each group to achieve total memory >= m, minimizing total cost (which is number of type1 selected + 2 * number of type2 selected? Actually b_i = 1 for regular, b_i = 2 for important, so cost is sum of b_i). So essentially we have items with weight a_i and cost c_i = b_i (1 or 2). Want to minimize cost subject to total weight >= m. That's a knapsack-like but with large a_i and n. But because costs are small (only 1 or 2), we can approach differently.
We can consider: For each possible number of type2 apps selected, we can find the best possible sum of memory from type1 apps to complement. Or we can sort apps in each type by descending memory, because we want to achieve a certain memory with minimal cost. Since cost per app is lower for type1 (cost 1) than type2 (cost 2), we would prefer using type1 apps if they provide enough memory. But maybe we need to use some type2 if type1 memory insufficient.
We need to minimize cost. Since cost is integer, and max total cost is at most 2*n (worst case remove all). But n up to 2e5 so we could try to compute something like: For each possible cost from 0 to something, check max memory achievable? Since costs small per item, maybe we can treat as two sets and use prefix sums after sorting descending.
Idea: Sort type1 apps by a_i descending, compute prefix sums of a_i. Similarly for type2. Let type1 list = A (size s1), sorted descending; type2 list = B (size s2), sorted descending.
We want to select x apps from type1 (cost x) and y apps from type2 (cost 2y). Total cost = x + 2y. Memory = sum of top x from A (since we would pick the ones with largest a_i to maximize memory for given count) plus sum of top y from B. So for each possible y (0..s2), we can compute the memory from type2: prefix2[y] (with prefix2[0]=0). Then we need to find minimal x such that prefix1[x] + prefix2[y] >= m. Since prefix1 is non-decreasing, we can binary search x. Then total cost = x + 2y. Then take min over y.
But we must ensure we consider the possibility of not picking any from one type. That's covered.
Complexities: O(s2 log s1) per test case, which could be up to O(n log n). Since total n <= 2e5, that's fine.
But careful: we need to consider also the case where we use only type1 or only type2. The binary search for x: we need prefix1 array to be long enough. If x > s1, then we cannot achieve with that y (unless we can also pick more type2? But we are iterating over y). In binary search we need to find smallest x such that sum >= m - prefix2[y]; if no such x (i.e., even with all type1, sum < needed), then skip this y.
But we can also do the reverse: iterate over x and binary search y. Since s2 may be larger, but both up to n.
But since s1 and s2 could be similar size, the complexity O(min(s1,s2) * log max) is okay.
But note: n total 2e5, t up to 1e4, so sum n is 2e5, so per test case can be up to 2e5. O(n log n) is fine.
We need to also handle large a_i and m up to 1e9, but prefix sums may exceed 32-bit, use 64-bit.
Edge Cases: If total memory sum of all apps < m, output -1. We could quickly compute total sum and skip.
But we also need to consider that we might remove some apps that are not the top ones? Since we want to maximize memory for a given cost, we would always pick the apps with largest memory for each type. Because cost only depends on the count of type1 and type2 selected, not on which specific apps. So to achieve a given total cost, the maximum memory achievable is indeed by picking the largest memory apps from each type. Since the types have different costs, but within each type cost per app is constant, sorting descending gives best memory per cost within that type.
Thus the approach is correct.
But we need to be careful: If we pick x type1 and y type2, total cost = x + 2y. But what if we could pick some type1 and type2 in a different combination that yields same cost but higher memory? For a fixed total cost C, we could choose y from 0 to floor(C/2) and x = C - 2y. Then we need to check maximum memory achievable with x type1 and y type2: it's prefix1[x] + prefix2[y] (if x <= s1, y <= s2). So we could iterate over y or over C. The approach of iterating y and binary search x already covers all combos.
But there is a nuance: If we iterate y from 0 to s2, we compute neededMem = m - prefix2[y]; if neededMem <= 0, then we can just use only type2 apps: cost = 2y, but we also could use less type2? Actually we are iterating y, so for that y we have cost 2y, but we could also add some type1 to reduce y? Wait we are iterating y and then adding x type1 to reach at least m. If neededMem <= 0, then we can achieve with just y type2 (x=0). That's fine: binary search would give x=0, but we must handle that: if neededMem <=0, then we don't need any type1; x=0. So we can set x=0 in that case.
Thus for each y, we compute needed = m - prefix2[y]; if needed <=0, cost = 2y; else we find smallest index x such that prefix1[x] >= needed; if x <= s1, cost = 2y + x; else cannot achieve with that y.
Then we keep minimum cost.
Time complexity: O(s2 log s1) or O(s2) with two-pointer? Could also use two-pointer to avoid binary search. Since as y increases, prefix2[y] increases, so needed decreases, so the required x is non-increasing. So we can maintain a pointer x from s1 downwards. Starting with y=0, find minimal x such that prefix1[x] >= m (or if not possible). Then as y increases, needed reduces, we can possibly decrement x. This yields O(s1 + s2). But binary search is fine given constraints.
However, we must also consider the possibility that we might need to pick all apps (both types) and still insufficient memory: then answer -1.
We can compute total memory sum_all = sum of all a_i. If sum_all < m -> -1.
Otherwise, we compute answer as described.
Now we test with sample.
Test 1: n=5,m=7 a=[5,3,2,1,4] b=[2,1,1,2,1] type1: b=1 -> apps: indices 2 (3),3(2),5(4) -> a:3,2,4 -> sort descending: [4,3,2]? Actually 4,3,2. prefix1: [0,4,7,9] type2: b=2 -> apps: indices1(5),4(1) -> a:5,1 -> sort descending: [5,1], prefix2: [0,5,6] Now iterate y=0: needed=7, need x min with prefix1[x]>=7 -> x=2 (prefix1[2]=7), cost=2 y=1: prefix2[1]=5, needed=2, x=1 (prefix1[1]=4>=2), cost=2*1+1=3 y=2: prefix2[2]=6, needed=1, x=1 (4>=1), cost=4+1=5 Min cost=2 -> answer 2. Correct.
Test2: n=1,m=3 a=[2], b=[1] type1: [2] prefix1 [0,2] type2: [] prefix2 [0] Total sum=2<3 -> -1. Good.
Test3: n=5,m=10 a=[2,3,2,3,2] b=[1,2,1,2,1] type1: indices1(2),3(2),5(2) -> [2,2,2] sorted descending: [2,2,2] prefix1 [0,2,4,6] type2: indices2(3),4(3) -> [3,3] prefix2 [0,3,6] Check total sum = 2+3+2+3+2=12 >=10. Iterate y=0: needed=10 -> need x? prefix1[?] max=6 <10, impossible. y=1: needed=10-3=7 -> need x? prefix1[3]=6<7, impossible. y=2: needed=10-6=4 -> need x=2 (prefix1[2]=4) cost=2*2+2=6 -> answer 6. Good.
Test4: n=4,m=10 a=[5,1,3,4] b=[1,2,1,2] type1: indices1(5),3(3) -> [5,3] sorted: [5,3] prefix1 [0,5,8] type2: indices2(1),4(4) -> [1,4] sorted: [4,1]? Actually descending: [4,1] prefix2 [0,4,5] Check total sum = 5+1+3+4=13>=10. y=0: needed=10 -> need x? prefix1[2]=8<10 impossible. y=1: needed=10-4=6 -> need x=2? prefix1[2]=8>=6 => x=2 cost=2*1+2=4 y=2: needed=10-5=5 -> need x=1 (5>=5) cost=4+1=5 Min cost=4. Good.
Test5: n=4,m=5 a=[3,2,1,2] b=[2,1,2,1] type1: indices2(2),4(2) -> [2,2] sorted: [2,2] prefix1 [0,2,4] type2: indices1(3),3(1) -> [3,1] sorted: [3,1] prefix2 [0,3,4] Total sum = 3+2+1+2=8>=5. y=0: needed=5 -> need x? prefix1[2]=4<5 impossible. y=1: needed=5-3=2 -> need x=1 (2>=2) cost=2*1+1=3 y=2: needed=5-4=1 -> need x=1 (2>=1) cost=4+1=5 Min cost=3. Good.
So algorithm works.
Implementation details:
- For each test case:
- read n, m
- read array a
- read array b
- Compute total memory sum_all = sum(a)
- If sum_all < m: print -1, continue
- Separate type1 and type2.
- vector mem1, mem2.
- For i=0..n-1: if b[i]==1 -> mem1.push_back(a[i]); else -> mem2.push_back(a[i]);
- Sort mem1 descending, mem2 descending.
- Build prefix sums for mem1: vector pre1(mem1.size()+1, 0) -> for i from 0 to size-1: pre1[i+1] = pre1[i] + mem1[i]. Similarly pre2 for mem2.
- Let s1 = mem1.size(), s2 = mem2.size().
- Initialize answer = INF (some large number, maybe 2n+5 because max cost <= 2n)
- For y from 0 to s2:
- sum2 = pre2[y]
- needed = m - sum2
- if needed <= 0: cost = 2y answer = min(answer, cost) // we could also break? But because as y increases cost increases? Not necessarily: cost = 2y, increasing with y, so after needed<=0, further y will have larger cost, but maybe we could have lower cost by using some type1? Actually if needed <=0, we have a valid solution with cost 2y. For larger y, cost increases, so no need to consider further y if we already have a solution? But careful: maybe we could combine with negative needed? No, needed <=0 already means we achieved memory >= m with just these y type2. Adding more type2 only increases cost, so not beneficial. But if we later consider larger y, cost becomes larger, so min would not be less. However, we might still need to consider adding type1 with smaller y? Wait we are iterating over y; if we have needed <=0 for current y, we have a solution with cost 2y. But maybe for a larger y, we could have cost that is even less? That would require 2y < 2y'? No, if y increases, 2y increases, so cost for larger y will be higher. So we can break after needed <=0? Not exactly: we are iterating y from 0 upward, so when we first encounter needed <=0, that gives cost = 2y. However, earlier y (smaller) didn't have needed <=0. So at this point we have found a valid solution, and any later y will have higher cost, so we can break out of loop. But there is also possibility that for some later y, we might combine with fewer type1? But if needed <=0 we already have cost 2y. Adding any type1 would increase cost. So no better. But if we break, we might miss some solutions that use both types but have lower cost than 2y? For example, suppose for y=3, needed <=0 => cost=6. But maybe for y=4, needed <=0? cost=8 >6. But maybe y=2 plus some type1 could give cost=22+1=5 which is less than 6. However that combo would be considered when y=2, not later. So we already considered y=2 before y=3. Since we iterate y increasing, we will see y=2 first. If for y=2, needed>0, we may find some x giving total cost maybe 5. Then y=3 might give needed<=0 and cost=6 which is worse. So break after needed<=0 would be safe because from that point onward, all solutions with only type2 (y) have cost at least 2y (which is >= current 2y). Solutions with y' > y and x>0 would have cost > 2y' > 2*y, so worse. So we can break. But be careful: we might have solutions with y'>y and x negative? No. So break is safe. However, we could also just continue but it's fine. But we might also break after needed<=0 but we also need to consider the case where we might still get better cost from combinations with x>0 for larger y that have small x? Actually consider scenario: type2 apps have huge memory but high cost, type1 apps have small memory but low cost. For some larger y, needed becomes negative, but maybe we could use fewer type2 and some type1 to get even lower cost? That would have been considered for that smaller y earlier. So if we break after needed<=0, we would have already processed all smaller y. So it's safe.
But careful: if needed <=0, we don't need to do binary search; just update answer and break.
- else needed > 0:
- Find x via binary search on pre1 (since pre1 is non-decreasing). We want smallest index x in [0, s1] such that pre1[x] >= needed. (pre1[0]=0). Use lower_bound on pre1 for needed. But careful: pre1 is monotonic increasing, so we can use std::lower_bound(pre1.begin(), pre1.end(), needed) - pre1.begin(). This returns index of first element >= needed. But that's the prefix length. Since pre1[0]=0, pre1[1]=first element sum, etc. The index returned is the x value? Actually if we have pre1 vector of length s1+1 where pre1[i] = sum of first i items (i from 0 to s1). Then the smallest i such that pre1[i] >= needed gives the number of items needed (i). So x = i. Then if x <= s1, then cost = 2*y + x. Else impossible for this y.
- Keep min answer.
But we must also handle that x can be 0? needed > 0, so x >=1. lower_bound will give at least 1.
Potential optimization: Since s1 and s2 could be up to 2e5, binary search O(log s1) per y is fine. But worst-case s2 could be 2e5, and O(s2 log s1) ~ 2e5*18 = 3.6 million, fine.
But we can also do two-pointer approach for O(s1+s2) which might be slightly faster but not necessary.
Edge Cases:
-
If s1=0: then we only have type2. We need to find smallest y such that pre2[y] >= m. If none, answer -1? But we already checked total sum, so there must be such y. So we can compute answer = 2 * (lower_bound on pre2). That's a special case. But our general loop with y from 0..s2 and with x binary search would still work: if s1=0, then pre1 only has [0]. For needed>0, we binary search and will not find any x>0 because pre1[1] doesn't exist. So only when needed <=0 (i.e., pre2[y]>=m) we get answer. So we need to ensure that for s1=0, we still compute answer. That's okay. But if total memory >=m but s1=0, there must be some y where pre2[y]>=m. So we will eventually find it in loop, and break. Good.
-
If s2=0, similar.
Now, complexity across test cases: sum n 2e5, so total O(N log N) fine.
But note: m up to 1e9, prefix sums up to sum a_i up to maybe 2e5 * 1e9 = 2e14, so need long long.
Implementation Steps:
For each test case:
- read n, m
- read list a (vector)
- read list b (int)
- compute total_sum = accumulate a
- if total_sum < m: output -1 and continue.
- vector v1, v2.
- for i in range(n): if b[i] == 1: v1.push_back(a[i]) else: v2.push_back(a[i])
- sort v1.rbegin(), v1.rend()
- sort v2.rbegin(), v2.rend()
- build prefix sums: vector pre1(v1.size()+1, 0); for i from 0 to v1.size()-1: pre1[i+1] = pre1[i] + v1[i]; similar pre2.
- s1 = v1.size(), s2 = v2.size()
- ans = INF (like 2*n+5)
- for y = 0; y <= s2; ++y: sum2 = pre2[y] needed = m - sum2 if needed <= 0: ans = min(ans, 2y) // Since cost increases with y, we can break? But we might have earlier better ans from combination with type1? Already considered. So break. break; // because any further y will have larger cost. else: // binary search on pre1 auto it = lower_bound(pre1.begin(), pre1.end(), needed); if (it != pre1.end()): x = it - pre1.begin(); ans = min(ans, 2y + x); // else cannot achieve with this y, continue
- Print ans.
But wait: is breaking on first needed <=0 always correct? Let's check scenario: Suppose for some y, needed <=0, cost = 2y. Could there be a later y' (greater) with combination (x>0) that yields cost less than 2y? Let's test: cost for y' > y: if we use x>0, total cost = 2y' + x. Since y' > y, 2y' >= 2*(y+1) = 2y+2. Even if x=1, total cost >= 2y+2 > 2y. So cannot be lower. If x=0, then needed <=0, cost = 2y' >= 2y+2 > 2y. So indeed cannot be lower. However, what if there is an earlier y (smaller) we haven't considered? But we are breaking only after we encountered needed <=0; we have already considered all smaller y because we are iterating increasing y. So we have already processed y=0,...,y_current-1. So any solution with smaller y we have considered; any solution with larger y will have cost >= current. So we can break.
But careful: There's also the possibility that for some y, needed <=0, but we might still have a solution with the same y but using some type1 as well that gives lower cost? No, using type1 adds positive cost, so it can only increase cost. So that's not beneficial.
Thus breaking is fine. But one must be sure that we have not missed solutions where needed >0 for current y but with a later y we might have needed <=0 and cost smaller than current min? But since we break when needed<=0, we stop and will not consider further y. But the answer might be from a later y? But later y would have higher cost than current 2y because cost=2y' > 2y. But maybe our current ans (before breaking) is not necessarily 2y; it could be something from previous y with combination, maybe larger than 2y. But wait, we break when needed<=0 at current y, we compute cost=2y and compare to ans. Then we break. But if earlier ans was something like 2y - 1? That's impossible because ans from previous combos could be lower than 2y. So it's possible that ans already holds a value less than 2y. In that case breaking is still safe because any later y gives cost >=2y >= ans? Actually if ans < 2y, then later y gives cost >=2y > ans, so not better. So breaking is fine. However, if ans is > 2y? Could happen: suppose we haven't found any valid solution before y, then ans=INF. Then we find needed<=0 at y, ans becomes 2y. That's the best possible because any later y yields larger cost. So we can break.
But there is a nuance: maybe we could have a solution with y' > y but with x negative? Not possible. So breaking is okay.
But what if needed <=0 but we haven't yet considered the possibility of using fewer type2? That's already considered. So yes break.
Thus we can break after first needed <=0. However, we need to make sure that if needed <=0 occurs at y, we update ans and then break. But we must also consider that there may be solutions where we use fewer type2 but more type1 that yields a lower cost than 2*y? Those would have been considered earlier (since y is smaller) as needed >0 case. So all good.
But we must also consider that maybe we can skip some type2 and use more type1 to get lower cost even if needed <=0? That would be a smaller y (since y smaller). Already considered.
Thus break after needed <=0 is safe.
But careful: In the loop, for y such that needed>0, we may find a valid x and compute cost=2y+x. That could be lower than future needed<=0 cost. So if we later hit needed<=0 with cost=2y' that is larger than current ans, we break anyway. So it's fine.
Now, one more nuance: The binary search we use on pre1 may be O(log s1). But we also can do two-pointer: Since as y increases, needed decreases, we can maintain x pointer starting from the smallest index such that pre1[x] >= needed. We can start with x = s1 (or use binary search) then decrement as needed decreases. This could be more efficient but not needed.
Now, let's consider possibility of overflow: pre1 and pre2 sums up to total sum, which may be up to 2e5 * 1e9 = 2e14, fits in 64-bit (long long). So use long long.
Now, need to handle case where answer remains INF (shouldn't if total_sum >= m, but consider possibility that total_sum >= m but we didn't find a valid combination because of limitations? Actually if total_sum >= m, we can take all apps: that's a valid set with cost = total convenience = sum of b_i. But is that always considered in our loop? If we take all apps, that corresponds to y = s2 (all type2) and x = s1 (all type1). In our loop, for y = s2, needed = m - pre2[s2]. pre2[s2] = sum of all type2 memory. Then needed = m - sum_type2. But note sum_all = pre1[s1] + pre2[s2] >= m, so needed <= pre1[s1]. So there will exist an x <= s1 such that pre1[x] >= needed. The binary search will give some x (maybe s1). Then cost = 2s2 + x. This is <= total cost (2s2 + s1). But it might not be exactly total cost if x < s1. Actually if needed is less than total type1 memory, then x might be less than s1. So our loop covers that. So there is always at least one valid combination (the full set) as long as total_sum >= m. So ans will be set.
Thus algorithm seems correct.
Now, we should also consider that we might have solution with only type1: y=0, needed=m, we find x using binary search. That's also included.
Thus overall correct.
But there is a nuance: The loop y from 0 to s2, but we break early if needed<=0. That may skip the case where needed<=0 occurs early but we haven't considered combination for that same y with x>0? Not needed.
Now test with a scenario: type1 apps memory small, type2 memory large. For m=10, type1: [1,1,1,...] many but cost 1 each, type2: [10] cost 2. total_sum>=10. The best might be to take one type2 app cost=2, while taking 10 type1 would cost 10. Our loop: y=0: needed=10, pre1[10]=10 if we have at least 10 type1? Actually if we have only 9 type1, then cannot; but we might have 10. For y=0, if s1>=10, cost=10, ans=10. y=1: sum2=10, needed<=0, cost=2, update ans=2, break. So we get min=2. Good.
Now consider scenario where combination is better: type2: [9] cost=2, type1: [2] cost=1, m=10. Total_sum=11>=10. Solutions: y=0: needed=10, pre1[1]=2 <10, impossible. y=1: sum2=9, needed=1, x=1, cost=2+1=3. So ans=3. If we had break on needed<=0? For y=1, needed=1>0, so no break. Then y=2: but s2=1 only. So loop ends. So no break. Good.
Now scenario where we have both types and for some y needed>0 but not enough type1, but later y needed<=0 gives a higher cost but still maybe lower than earlier combos? Suppose early combos gave high cost, later needed<=0 gives lower? Actually needed<=0 occurs when sum2 >= m. So cost=2y. Since y is increasing, cost is increasing. So later needed<=0 cannot be lower than earlier needed<=0 if earlier had y' < y. But earlier needed<=0 only occurs at some y' when sum2[y'] >= m. If that y' exists, it will be the first y where sum2 >= m. So it gives minimal y such that sum2 alone suffices, which yields the minimal 2y among all type2-only solutions. Since earlier y with sum2<m can't be type2-only solutions. So the break at first needed<=0 gives minimal type2-only solution. And any combination with type1 might give cost less than that if type1 are cheap enough. Those combinations will be considered for y < that first y. So we need to consider all y from 0 up to (first y where sum2>=m) - 1, and also that y itself. But if we break at first needed<=0, we will have considered y up to that point (including that y)? Our loop: for y from 0 to s2, we compute needed. If at y = y0 we get needed<=0, we compute cost and then break. That means we have considered y0, but we have not considered y > y0. That's fine because they're worse. But we have considered all y < y0. So we have considered all combinations where y < y0 and possibly y0 with x>0? Actually at y0, needed<=0, we only considered x=0 because we just updated cost=2y0 and break. But could there be a solution with y0 and some x>0 that gives lower cost? That would be cost = 2y0 + x, which is > 2*y0, so not lower. So we don't need to consider it.
Thus break is safe.
So algorithm works.
Now, consider potential pitfalls:
- Using lower_bound on pre1 which is sorted ascending. That's fine.
- Edge case: pre1 empty (s1=0). Then pre1 = [0]. lower_bound for needed>0 will return pre1.end() (since only 0 not >= needed). So we skip.
Now, complexity is fine.
Now, could there be a scenario where we need to consider that we can also take apps not as the top ones because maybe we need to meet memory exactly while minimizing convenience? Since convenience points are not dependent on memory size, we always want to maximize memory per cost. Within a given type, cost per app is fixed, so we want to pick the largest memory apps to maximize memory for a given number of apps. So sorting descending is optimal.
Now, we need to ensure we don't exceed time/memory. Sum n 2e5, t up to 1e4. But reading input and processing should be fine.
Now, we should implement accordingly.
But before writing final solution, let's consider alternative viewpoint: The problem can be seen as a variant of knapSack with two item types and we want to minimize cost given memory target. Since costs are small (1,2), we could also compute for each possible total cost C (from 0 to 2n) the maximum memory achievable. This can be done by DP but would be O(n^2) not possible. So the sorting approach is efficient.
But is there any scenario where picking not the largest memory apps from a type could yield a lower total cost for a given memory target? Let's think: Suppose we have two type1 apps: a=[10,1] and we need m=10. Picking the larger one gives cost 1. That's optimal. Suppose we need m=11, we need both, cost 2. That's also optimal. If we need m=10 and we pick the smaller one, we still need another app, so cost 2, worse. So sorting descending works.
For type2, similar.
What about mixing? We always want to maximize memory per cost? But cost per unit memory not uniform across types. Type1 gives memory per cost 1, type2 gives memory per cost 2. So if we compare a type1 app with memory X and a type2 app with memory Y, we might prefer type2 if Y is very large compared to X? But cost for type2 is 2. So the decision about which type to use and how many is captured by iterating over y and computing x.
But is it ever beneficial to not pick the largest type2 apps? Suppose we have two type2 apps: [100, 1] and many type1 apps: [50, 50, ...]. For m=101, we could pick type2 100 and type1 1 (if there is a 1) cost=2+1=3. If we instead pick type2 1 and type1 100? But type1 100 might not exist, but suppose type1 has 99? Actually if we pick the smaller type2 and then need more type1, cost could be higher. But picking the larger type2 first is always beneficial because for a given number of type2 (y), we want to maximize sum2 to reduce needed type1. So we should pick largest type2. So sorting descending is correct.
Thus approach stands.
Now, note that we could also try a greedy: try to use type2 first, but that may not be optimal? For instance, sometimes using a type1 may be cheaper. But our enumeration covers all.
Now, handle large t and sum n, we should be careful with resetting vectors and using fast I/O.
Implementation Plan:
-
Use scanf/printf or cin with ios_base::sync_with_stdio(false); cin.tie(0); to speed up.
-
In each test case:
- Read n, m (int, long long? m up to 1e9, fits in int32 but we might use long long for safe.)
- vector a(n), b(n). Or read a_i into long long.
- Compute total_sum = accumulate.
- If total_sum < m: print -1 and continue.
- Separate:
- vector v1, v2.
- For i=0..n-1: if b[i]==1: v1.push_back(a[i]) else v2.push_back(a[i]).
- Sort both descending:
- sort(v1.begin(), v1.end(), greater());
- sort(v2.begin(), v2.end(), greater());
- Build prefix sums:
- vector pre1(v1.size()+1); pre1[0]=0; for i=0..v1.size()-1: pre1[i+1]=pre1[i]+v1[i];
- Similarly pre2.
- Iterate as described.
Potential pitfalls:
-
If v1 is empty, pre1 has size 1 (only 0). lower_bound on pre1 for needed>0 will return pre1.end(), we handle that.
-
If v2 is empty, loop y from 0 to 0, works.
-
We can set ans = INF = 1e18.
-
In loop for y: sum2 = pre2[y]; if (sum2 >= m) { ans = min(ans, 2y); break; } else { // need some type1 long long need = m - sum2; // binary search on pre1 auto it = lower_bound(pre1.begin(), pre1.end(), need); if (it != pre1.end()) { int x = it - pre1.begin(); ans = min(ans, 2y + x); } }
-
Print ans.
Now, we should test on provided examples.
Let's code quickly in mind or run through.
But there is one more nuance: The binary search on pre1 gives the smallest x such that pre1[x] >= need. However, pre1 is size s1+1, with index 0..s1. If need is exactly pre1[x], it's fine. If need is larger than pre1[s1], it returns pre1.end().
Now, is it always optimal to take exactly the smallest x? Since cost increases with x, we want minimal x achieving the memory. So yes.
Now, is there any scenario where taking more type1 than needed could reduce type2 usage? But we are iterating y, so for each y we fix the number of type2. Within that, we choose minimal x. So that's optimal for that y. Overall min over y gives global optimum.
Thus algorithm correct.
Now, consider time: For each test case, we sort two vectors. Sorting O(s1 log s1 + s2 log s2) <= O(n log n). Since sum n 2e5, okay.
But we can also avoid sorting all vectors if we do a different approach? Not needed.
Now, we should be careful about memory: vectors within each test case, but sum n small.
Now, also note: m can be large but we use long long.
Now, confirm sample output:
Already did.
Now, let's test some edge cases.
Case 1: n=2, m=1, a=[1,1], b=[2,1]. total_sum=2>=1. v1: [1], v2:[1] (since b1=2? Actually b=[2,1] -> type2 first, type1 second). pre1: [0,1], pre2: [0,1]. y=0: need=1, binary search pre1 -> x=1, cost=0+1=1. y=1: sum2=1 >= m => cost=2*1=2, ans = min(1,2)=1. Output 1. That seems correct: remove type1 app cost 1.
Case 2: n=2, m=1, a=[1,1], b=[2,2] both type2. pre1 empty [0]. pre2 [0,1,2]? Actually v2 has two items both size1, sorted descending [1,1] pre2: [0,1,2]. y=0: need=1, binary search pre1 returns end -> skip. y=1: sum2=1 >= m, cost=2, ans=2. So output 2. That's correct: need to remove one type2 cost 2.
Case 3: n=2, m=3, a=[2,2], b=[1,2]. total=4>=3. v1: [2] pre1[0,2]; v2: [2] pre2[0,2]. y=0: need=3, binary search pre1: pre1[1]=2<3, pre1[2]? s1=1, only pre1[0], pre1[1]; so no. y=1: sum2=2, need=1, binary search pre1: x=1 (pre1[1]=2>=1) cost=2+1=3. So answer 3. Check: Could we remove both apps? Cost=1+2=3, memory=4>=3, same cost. So 3 is correct.
Now, test a scenario where we need to consider many type1 and type2.
Now, about break condition: we break on sum2>=m. But what if there is a solution with y such that sum2>=m but we haven't yet considered a solution with a smaller y that uses some type1 which could be cheaper? That's considered earlier, so it's fine. So break after updating ans (if needed). But we must make sure that we compute ans for that y as well. Actually if sum2>=m at y, we compute cost = 2*y, update ans, then break. This is the smallest y that yields sum2>=m. But there could be an even smaller cost from a combination with y' < y that uses type1; that would have been considered already. So break is fine.
Now, check scenario: type2: [100] (cost 2, memory 100), type1: [99] (cost 1, memory 99), m=100. y=0: need=100, binary search pre1: x=1 (99<100) No because pre1[1]=99<100, pre1 has only one element, pre1[1]=99 <100, so no valid x. So skip. y=1: sum2=100 >=m, cost=2, ans=2. So answer 2. That's correct: remove the type2 app.
Now scenario: type2: [100], type1: [100], m=100. y=0: need=100, x=1 cost=1. ans=1. y=1: cost=2, not better. So ans=1.
Now, scenario where type2-only is cheaper than mixed? Actually type2 cost is 2 per app, type1 is 1 per app, so type2 is more expensive per app. So type2-only solution cannot be cheaper than mixed if mixed uses type1. So break is still fine.
Now, ensure to use long long for needed and sums.
Now, one more check: The condition for breaking after sum2>=m relies on the fact that cost=2*y increases with y. But if we break early, we might miss a situation where for some y > that y, we could have a solution with x negative? No. So fine.
Now, implement.
But consider if we break and then we haven't processed the case where at that y, maybe we could have used fewer type2 and some type1 to achieve cost less than 2*y? That would be a smaller y, so already considered.
Thus good.
Now, we must also consider that the answer could be larger than 2n? Actually maximum cost is sum b_i which is at most 2n, so INF can be something like 1e18.
Now, test a more complex scenario with many items to verify the two-pointer approach not needed but binary search fine.
Now, note: Since we break early, the loop might not go through all y. That's fine.
Now, there's a potential for optimization: If we precompute for each possible x (or y) but fine.
Now, let's test the algorithm with random data via mental or small script? I'll trust.
Now, double-check the constraints: t up to 1e4 but sum n 2e5, so many small test cases possible. The sorting per test case of size up to maybe 20,000? But sum 2e5, so overall sorting O(total n log n) but each test case sorting individually might sum to O(∑ n_i log n_i). Since sum n_i is 2e5, worst-case if one test case has n=2e5, then sorting that is O(2e5 log 2e5). That's fine.
Now, let's implement.
But I recall a similar problem from Codeforces: "Polycarp and Phone" maybe "Applications" or something. Often there is a solution using sorting and two-pointer. So our approach is standard.
Now, there might be a nuance: We need to free at least m memory, not exactly m. Our binary search finds minimal x such that pre1[x] >= needed, which ensures sum1 + sum2 >= m. That's correct.
Now, edge case: When needed <=0, we set cost=2y. But could there be a case where needed == 0? That means sum2 exactly equals m, cost = 2y. That's fine.
Now, what about if we have both types, and we could achieve memory >= m with some x and y, but cost = 2*y + x. Since we are taking min, fine.
Now, we might also consider possibility of using more type1 than necessary for a given y to reduce y? Not relevant because we fixed y.
Thus done.
But I want to test a scenario where the optimal solution uses many type2 because type1 memory is insufficient, but also there is a solution with many type1 (more count) that might have lower cost? Since type1 cost 1, many type1 could be cheaper even if they are many? Actually type1 each cost 1, so if we need to take many type1, cost is number of type1. If we take some type2, each costs 2. So if we can replace two type1 (cost 2) with one type2 (cost 2) but the memory of one type2 might be more or less than two type1. So it's a trade-off. Our enumeration over y explores all possibilities.
Now, consider the possibility of using a type2 instead of two type1 if it provides more memory. That's captured.
Now, let's check a scenario where both types have same memory distribution but different costs. For example, many small type1 and few large type2. Our algorithm will find optimal.
Now, let's verify using a custom case:
n=3, m=5 a=[2,2,4] b=[1,1,2] // third is type2 with memory 4. v1=[2,2], sorted [2,2], pre1:0,2,4 v2=[4], pre2:0,4
y=0: need=5 -> pre1[2]=4<5, pre1[3]? not exist, skip. y=1: sum2=4, need=1 -> x=1 (pre1[1]=2>=1) cost=2+1=3. Thus answer 3 (remove type2 and one type1). But could we remove two type1 (cost 2) and no type2? That gives memory 4 <5, not enough. Remove all three? cost=1+1+2=4, memory=8>=5, cost 4 >3. So optimal is 3. Good.
Now, another case: n=3, m=4 a=[2,2,4] b=[1,1,2] y=0: need=4 -> x=2 (pre1[2]=4) cost=2 So answer 2. That's better than using type2.
Now, all good.
Now, confirm with a larger case to check break condition: Suppose v2 has many items, first time sum2>=m at y=10, cost=20. But maybe combination with y=9 and x=some could be cost less than 20? Let's see: For y=9, cost = 18 + x. If x <= 1, cost <=19 <20, so better. That would be considered before y=10. So break at y=10 is fine.
Now, what if v2 memory is exactly such that sum2 just crosses m at y=10, and the best combination is with y=11 and x=0? That's cost=22, worse. So break fine.
Now, but what if there is no y such that sum2 >= m? Then we never break, loop all y, and eventually consider combination with full v2 and v1. That's fine.
Now, we must be careful about using int for loop indices and x; but cost could be up to 4e5? Actually max cost = sum b_i <= 2*2e5 = 4e5, so we can store ans in int. But for safety use long long.
Now, potential issues with lower_bound on vector if we use pre1 as long long; lower_bound works.
Now, confirm memory: using vector push_back and clear each test case; total memory fine.
Now, let's produce final answer.
But wait, is there any scenario where we need to consider not using all top x items from type1? Could there be a situation where picking a lower-memory type1 app instead of a higher one allows us to pick a different type1 app? But all type1 are identical in cost, so picking the largest gives maximum memory for that count. So if we can achieve needed memory with x items, picking the largest x yields at least as much memory as any other set of x items. So it's optimal.
Thus algorithm is sound.
Now, we could also consider using a two-pointer approach to avoid binary search and perhaps be faster. But not needed.
Now, test with a tricky scenario where both type1 and type2 have many items and we need to combine them. Our algorithm enumerates y from 0 to s2 and for each binary search. That's O(s2 log s1). In worst case s1 ~ s2 ~ 1e5, s2 log s1 ~ 1e5 * 17 = 1.7 million, fine.
But note: total test cases up to 1e4, but sum n 2e5, so worst-case average n per test small. So overall operations ~ 2e5 * log(2e5) maybe 2e5 * 18 = 3.6 million, fine.
Now, let's consider potential improvements: We could also iterate over x and binary search y. But not needed.
Now, implementation details:
We'll write solve() function.
Pseudo-code:
int main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while (t--) { int n; long long m; cin >> n >> m; vector a(n); for (int i=0; i<n; ++i) cin >> a[i]; vector b(n); for (int i=0; i<n; ++i) cin >> b[i];
long long total = accumulate(a.begin(), a.end(), 0LL); if (total < m) { cout << "-1\n"; continue; } vector<long long> v1, v2; for (int i=0; i<n; ++i) { if (b[i] == 1) v1.push_back(a[i]); else v2.push_back(a[i]); } sort(v1.rbegin(), v1.rend()); sort(v2.rbegin(), v2.rend()); vector<long long> pre1(v1.size() + 1), pre2(v2.size() + 1); for (int i=0; i<(int)v1.size(); ++i) pre1[i+1] = pre1[i] + v1[i]; for (int i=0; i<(int)v2.size(); ++i) pre2[i+1] = pre2[i] + v2[i]; long long ans = LLONG_MAX; int s1 = v1.size(), s2 = v2.size(); for (int y=0; y<=s2; ++y) { long long sum2 = pre2[y]; if (sum2 >= m) { ans = min(ans, 2LL * y); break; } long long need = m - sum2; auto it = lower_bound(pre1.begin(), pre1.end(), need); if (it != pre1.end()) { int x = it - pre1.begin(); ans = min(ans, 2LL * y + x); } } cout << ans << "\n"; } return 0;}
Now, check that we used pre1 and pre2 correctly. pre1[0]=0.
Now, check potential integer overflow: 2*y where y up to 2e5 fits in 32-bit, but we use long long.
Now, ensure that we use lower_bound on pre1 which includes pre1[0]..pre1[s1]. That works.
Now, edge case: v1 empty, pre1 = [0]. For need>0, lower_bound returns end, so we skip.
Now, consider if v1 empty and v2 empty? n>=1 so at least one.
Now, answer will be set because total >= m, so at least the combination with all apps works. For y = s2, sum2 = pre2[s2] = total_v2. need = m - total_v2. Since total = total_v1 + total_v2 >= m, need <= total_v1. But if v1 empty, need <=0, so we would have broken earlier with y such that sum2 >= m? But if v1 empty and total >= m, then total_v2 >= m. So there will be some y (the smallest y where sum2 >= m) that triggers break and sets ans. So all good.
Now, what about scenario where v1 non-empty but pre1[s1] is not enough to cover need? Actually total >= m ensures need <= total_v1. So for y=s2, need <= total_v1, so pre1[s1] = total_v1 >= need, so lower_bound will find some x <= s1. So ans will be set.
Thus ans always gets updated.
Now, potential off-by-one: The prefix arrays: pre1[0] = 0. If need is 0, we would handle sum2>=m branch. So need>0 always for binary search branch.
Now, confirm with sample 3: v1: [2,2,2] pre1: [0,2,4,6]; v2: [3,3] pre2: [0,3,6]. For y=0, sum2=0<7? m=10? Actually m=10. sum2=0, need=10, lower_bound returns pre1[3]=6<10? Actually pre1[3]=6, need=10 >6, so lower_bound returns pre1.end()? Wait pre1 has size 4, with indices 0..3. pre1[3]=6. lower_bound for 10 returns pre1.end(). So skip. y=1: sum2=3, need=7, lower_bound pre1: pre1[3]=6<7, returns end. y=2: sum2=6, need=4, lower_bound pre1: first pre1 >=4 is pre1[2]=4, x=2. cost=4+2=6. ans=6. So good.
Now, test scenario where need exactly equals a prefix sum: m=8 in above? Not needed.
Now, implement.
Now, one more test: n=5, m=7, a=[5,1,1,1,1], b=[2,1,1,1,1]. v1: [1,1,1,1] pre1: 0,1,2,3,4; v2: [5] pre2:0,5. y=0: need=7, pre1[4]=4<7, skip. y=1: sum2=5, need=2, pre1[2]=2, x=2, cost=2+2=4. So ans=4. But is there better? Could we remove type2 only? cost=2, memory=5<7, not enough. Could we remove all type1? cost=4, memory=4<7, not enough. So ans=4 seems right.
Now, confirm: If we remove type2 and two type1, memory=5+2=7, cost=2+2=4. Yes.
Now, we could also remove three type1? That would be memory=3<7, no. Remove four type1 and type2? cost=1*4+2=6, memory=5+4=9, cost 6 >4. So 4 is minimal.
Now, test if break works: y=1, sum2=5 <7, so no break. y=2 not possible since s2=1. So ans=4. Good.
Now, think about the correctness of using lower_bound: Since pre1 is non-decreasing, the smallest i with pre1[i] >= need gives the minimal number of type1 needed. This is correct because we want minimal x.
Now, we need to be careful: The prefix array includes pre1[0]=0; if need is 0, we would treat earlier, so fine.
Now, I think it's correct.
Now, for performance, we might want to use vector for pre1, pre2.
Now, final code.
But we need to be careful about the reading: b_i are integers, but they are either 1 or 2, so we can read as int.
Now, a_i up to 1e9, m up to 1e9, but prefix sums can be up to 2e14, use long long.
Now, output ans as long long.
Now, let's also consider an alternative: Because we break early, but we might need to also consider the case where we don't break because sum2 never reaches m. That's fine.
Now, test a case where there is a large number of type2 and type1 but the optimal solution uses a combination where y is near s2 but x is small? For example, v2 items are all small, v1 items are large. Suppose v2: many 1s, v1: one 1000. m=1000. The type2-only solution would need y=1000 if each gives 1, cost 2000. But using one type1 gives cost 1, better. Our algorithm: y=0: need=1000, binary search pre1: x=1 (1000>=1000) cost=1, ans=1. So break not reached. Good.
Now, scenario where both types have large numbers but optimal uses many type2 because type1 not enough? Already covered.
Now, check potential overflow in sum2: sum2 can be up to total_v2, which is sum of a_i for type2, up to total sum <= 2e14, still fits in long long.
Now, finalize.
But note: In the loop, we are using 'auto it = lower_bound(pre1.begin(), pre1.end(), need)'. This works if pre1 is sorted ascending. Since pre1 is increasing, yes. However, we must ensure pre1 is built from descending sorted v1; but prefix sum of descending sorted v1 is still non-decreasing as we add more elements (since we add positive numbers). So it's sorted ascending. That's fine.
Now, note: Could there be any tie-breaking where we need to consider that maybe using more type1 than necessary could allow using fewer type2? That's not captured by fixing y. But we are iterating over y, so for each possible y, we choose minimal x. That covers all combinations. So we consider all possible numbers of type2.
Now, is there a possibility that the optimal solution uses some type2 and some type1, but not the largest ones? For a given y, the maximum sum2 is achieved by taking largest y type2. To achieve a given memory target, if we can achieve it with a particular set of y type2 and x type1, then using the largest y type2 yields at least as much sum2, potentially reducing the needed x. So for that y, the cost using largest items is at most the cost using any other selection of y type2. Since we minimize x, it's optimal to take largest. Similarly, for given y, using largest x type1 yields maximal sum1, so if we can achieve target with some selection of x type1, then using largest x will also achieve it (maybe with even larger margin). But we need minimal x; if we consider all y, we will find the minimal cost overall.
Thus correct.
Now, I'll produce final answer.
But we should double-check that we need to output minimum convenience points lost. That's cost.
Now, the problem statement has an example where they output 3 for the fifth test case. We tested that.
Now, possible alternative: Use two-pointer to avoid binary search, but it's not necessary.
Now, I will produce the code in the answer.
But I'll also think about potential pitfalls with using lower_bound: The pre1 vector contains long long values; need is long long. Should work.
Now, check if we need to handle extremely large m up to 1e9 but prefix sums might be up to 2e14, so comparisons fine.
Now, we might also need to consider that a_i can be 1e9, n up to 2e5, total sum up to 2e14, which fits in signed 64-bit (max 9e18). Good.
Now, I'll produce final solution in C++.
One more thing: In the loop, we break after sum2>=m, but we should still update ans before breaking. That's done.
Now, is there any case where the best solution is a combination that includes some type2 and type1, but the cost equals 2y + x and this is lower than any solution with fewer type2 (including possibly type2-only) but we break before checking that combination because sum2>=m happened earlier? No, because sum2>=m at y0. If there is a solution with y1 > y0 that is cheaper, then 2y1 + x < 2y0? Since y1 > y0, 2y1 >= 2y0+2, even if x=0, 2y1 >= 2y0+2 > 2y0. So cannot be cheaper. If x is negative? Not allowed. So no.
Now, consider scenario: sum2>=m at y0, but the solution we found for y0 (type2-only) has cost 2y0. Could there be a solution with y0 and some type1 that has cost < 2y0? That would require x < 0, impossible. So no.
Thus break is fine.
Now, ensure that we use long long for ans and intermediate multiplication 2y. y is int but can be up to 2e5, 2y fits in int, but for safety use 2LL*y.
Now, I think it's correct.
Now, let's test additional cases manually.
Case: n=4, m=10, a=[6,5,5,5], b=[1,2,2,2]. v1: [6]; v2: [5,5,5] sorted: [5,5,5]; pre1: [0,6]; pre2: [0,5,10,15]. y=0: need=10, pre1[1]=6<10, skip. y=1: sum2=5, need=5, binary search pre1: need=5, pre1[1]=6>=5 -> x=1, cost=2+1=3. y=2: sum2=10>=10 -> cost=4, ans = min(3,4)=3. So answer 3. Check: removing one type2 (cost 2, memory 5) and one type1 (cost 1, memory 6) total memory 11, cost 3. Is it possible? Yes. Could we do two type2? cost 4 memory 10, cost 4 >3. So 3 is optimal. Good.
Now, case where we need to use more than one type1 but type2 cheap? Actually type2 cost higher, but maybe combination yields cheaper if type1 many and type2 many? Not likely.
Now, all good.
Now, think about alternative solution: Some might try greedy: sort all apps by memory per cost ratio? But not needed.
Now, implement.
Potential improvements: Since we are breaking early, we could also start loop from y=0 and go up, but break when sum2 >= m. That's fine.
But we must be careful: if we break early, we still need to consider the case where we have not yet considered some y that could lead to a lower cost due to using type1? Actually if sum2 >= m, we break. That's the first y where sum2 >= m. For any y < that, sum2 < m, so we needed type1. Those were considered. For y > that, cost higher. So break.
Thus code is correct.
Now, let's test with random small n to ensure no oversight.
We could write a brute force for n up to 10 to verify our algorithm against brute force, but here we can't run code. We'll trust.
Now, edge: m=0? According to problem, m >= 1. So no zero.
Now, all good.
Now, final solution.
But there's another nuance: The total sum of n across test cases is 2e5, but there is t up to 1e4. Our code uses dynamic vectors each test case. The sum of sizes across test cases is 2e5, so total memory is fine.
Now, we should flush output? Usually not.
Now, provide final answer.
But before finalizing, let's double-check the problem statement's constraints: "n (1 ≤ n ≤ 2·10^5)" per test, but sum of n over all test cases <= 2·10^5. So our algorithm's complexity is fine.
Now, we could also do the loop in reverse: iterate x and find y, but same.
Now, final answer.
One more potential issue: If both v1 and v2 are large, and we break early, we might not get to consider y values where sum2 is not enough but combination with type1 yields lower cost than the type2-only solution at the break point. But as argued, those y are less than break point, and we consider them. So okay.
Now, test scenario: v2 = [100, 1], v1 = [1,1,1,... many ones]. m = 100. The first y where sum2 >= m? At y=1, sum2=100 >= m, break with cost=2. But is there a combination with y=0? y=0 need=100, need many type1. Suppose we have 100 type1 of size 1, then x=100, cost=100 >2. So break is correct. Suppose we have 99 type1 of size 1, then total sum = 99 + 101? Actually v2: [100,1] total type2=101. m=100. y=0: need=100, but type1 total = 99, not enough, so no solution with y=0. y=1: sum2=100 >= m, cost=2. So break. So answer 2. Good.
Now, scenario: v2 = [100, 1], v1 = [99]. m=100. y=0: need=100, pre1[1]=99<100, no. y=1: sum2=100>=m, cost=2, ans=2. So answer 2. Could there be combination with y=1 and x=0? That's same. So break.
Now, scenario: v2 = [99, 1], v1 = [100]. m=100. y=0: need=100, pre1[1]=100, x=1 cost=1, ans=1. Break condition? sum2 at y=0 =0<100, so no break. So ans=1. Good.
Now, scenario: v2 = [50, 50], v1 = [1,1,... many]. m=100. y=0: need=100, but type1 sum? maybe insufficient. y=1: sum2=50, need=50, pre1 maybe need 50 but type1 might not have 50? Suppose type1 have sum 40 only, then need=50 can't be met. y=2: sum2=100 >= m, cost=4, ans=4. But is there a better combination? Could use one type2 (50) and 50 type1? But if type1 sum only 40, then can't. So answer 4. So break at y=2 works.
Now, scenario: v2 = [50, 50], v1 = [60]. m=100. y=0: need=100, pre1[1]=60<100, no. y=1: sum2=50, need=50, pre1[1]=60>=50 -> x=1 cost=2+1=3. ans=3. y=2: sum2=100 >= m, cost=4, not better. So break at y=2 after computing cost=4? But we don't break because before y=2 we didn't break; we break when sum2>=m at y=2, but we should still compute cost=4 and compare, then break. In our loop, we check if sum2>=m: then update ans and break. So at y=2, we set ans = min(prev ans, 4) = 3 remains, then break. So correct.
Now, ensure we don't skip y=2's combination with x>0? But sum2>=m, so x=0 is optimal for that y. So fine.
Now, I think it's done.
Now, let's also consider if we can avoid binary search by using two-pointer. But not necessary.
Now, produce final answer.
One more thing: If v1 is empty, we will have pre1 = [0], and for need>0 lower_bound returns end. So only solutions considered are those where sum2>=m. That's fine.
Now, a potential bug: In the for loop, we used int y up to s2. s2 can be up to 2e5, which is fine. However, ans can be large. But we set ans initially to a big number like 1e18.
Now, we must ensure that we don't have overflow in pre1 and pre2 accumulation. Use long long.
Now, final code.
After writing, we can test sample input.
But there is another nuance: The problem's memory limit? Not specified, but typical 256 MB. Our vectors of size n, fine.
Now, I'll proceed to write the final solution.
However, I've just realized that there might be an even simpler solution: Since b_i is only 1 or 2, we can treat the cost as number of apps removed + number of important apps removed (since important apps cost extra 1? Actually each important app costs 2, regular costs 1, so the cost is #regular + 2*#important = total apps removed + #important removed. But not needed.
Now, final answer.
I will produce final code below.
But before final, let's think about possible alternative edge case: If m is very large, e.g., 1e9, but total sum is just >= m, then pre2[y] may never reach m until y=s2, but we still need to consider combination. Our loop goes all the way to s2. So fine.
Now, complexity: In worst-case s2 = 2e5, we loop through all. That's okay.
Now, test sample 3: Already done.
Now, I think it's ready.
Now, I'll produce final answer with explanation.
One more thought: In the for loop, we compute sum2 = pre2[y] each time. That's O(1). Good.
Now, final answer. ```cpp #include <bits/stdc++.h> using namespace std;
typedef long long ll;
void solve() { int n; ll m; cin >> n >> m; vector a(n); for (int i = 0; i < n; ++i) cin >> a[i]; vector b(n); for (int i = 0; i < n; ++i) cin >> b[i];
ll total = accumulate(a.begin(), a.end(), 0LL); if (total < m) { cout << "-1\n"; return; } vector<ll> reg, imp; // regular (b=1), important (b=2) for (int i = 0; i < n; ++i) { if (b[i] == 1) reg.push_back(a[i]); else imp.push_back(a[i]); } // sort descending to maximise freed memory for a given count sort(reg.rbegin(), reg.rend()); sort(imp.rbegin(), imp.rend()); // prefix sums vector<ll> pre1(reg.size() + 1, 0); for (size_t i = 0; i < reg.size(); ++i) pre1[i+1] = pre1[i] + reg[i]; vector<ll> pre2(imp.size() + 1, 0); for (size_t i = 0; i < imp.size(); ++i) pre2[i+1] = pre2[i] + imp[i]; ll ans = LLONG_MAX; int sz1 = reg.size(), sz2 = imp.size(); for (int y = 0; y <= sz2; ++y) { ll sum2 = pre2[y]; if (sum2 >= m) { // enough with only important apps ans = min(ans, 2LL * y); break; // further y would only increase the cost } ll need = m - sum2; auto it = lower_bound(pre1.begin(), pre1.end(), need); if (it != pre1.end()) { int x = it - pre1.begin(); // minimal number of regular apps ans = min(ans, 2LL * y + x); } // if it == pre1.end() then this y cannot be extended with regular apps } cout << ans << "\n";}
int main() { ios_base::sync_with_stdio(false); cin.tie(0);
int t; cin >> t; while (t--) { solve(); } return 0;}
- For each test case: