# k-Capable Model Selection
## Problem Statement
You are given $n$ machine learning models. Each model $i$ (for $0 \le i < n$) is characterized by two attributes: its cost, denoted by $\text{cost}_i$, and its feature compatibility, represented by a binary string $\text{featureAvailability}_i$ of length $2$. The interpretation of this string is as follows:
* `"00"`: Not suitable for either Feature A or Feature B.
* `"01"`: Suitable for Feature A only.
* `"10"`: Suitable for Feature B only.
* `"11"`: Suitable for both Feature A and Feature B.
A set of models is defined as **$k$-capable** if it satisfies two conditions:
1. The number of models in the set that are suitable for Feature A is at least $k$.
2. The number of models in the set that are suitable for Feature B is at least $k$.
Your task is to compute, for each integer $k$ from $1$ to $n$, the minimum total cost required to assemble a **$k$-capable** set of models. If it is not possible to form a $k$-capable set for a particular $k$, you should report $-1$ for that value of $k$.
## Input Format
- The first line contains a single integer $n$ ($1 \le n \le 2 \times 10^5$), representing the number of machine learning models.
- The second line contains $n$ integers $\text{cost}_0, \text{cost}_1, \dots, \text{cost}_{n-1}$ ($0 \le \text{cost}_i \le 10^9$), where $\text{cost}_i$ is the cost of the $i$-th model.
- The third line contains $n$ binary strings $\text{featureAvailability}_0, \text{featureAvailability}_1, \dots, \text{featureAvailability}_{n-1}$, where $\text{featureAvailability}_i \in \{\text{"00"}, \text{"01"}, \text{"10"}, \text{"11"}\}$ is the feature compatibility string for the $i$-th model.
## Output Format
Output a single line containing $n$ integers, separated by spaces. The $(j+1)$-th integer in this line (for $0 \le j < n$) should represent the minimum total cost to form an $(j+1)$-capable set of models. If it is not possible to form an $(j+1)$-capable set, output $-1$.
## Sample Test Cases
### Sample Input 1
```
6
3 6 9 1 2 5
10 01 11 01 11 10
```
### Sample Output 1
```
2 6 15 26 -1 -1
```
## Constraints
- $1 \le n \le 2 \times 10^5$
- $0 \le \text{cost}_i \le 10^9$
- $\text{featureAvailability}_i \in \{\text{"00"}, \text{"01"}, \text{"10"}, \text{"11"}\}$
- Time limit: 1 second
- Memory limit: 256 MB
## Explanation
Let's analyze the given sample input:
$n=6$
Costs: $[3, 6, 9, 1, 2, 5]$
Feature Availability: $["10", "01", "11", "01", "11", "10"]
We categorize models based on their feature compatibility. Models with compatibility `"00"` are not useful for satisfying the $k$-capable conditions, so we only consider models suitable for Feature A, Feature B, or both.
| Original Index | Cost | Feature Availability | Category |
|----------------|------|----------------------|-------------|
| 0 | 3 | `"10"` | Type B only |
| 1 | 6 | `"01"` | Type A only |
| 2 | 9 | `"11"` | Type AB |
| 3 | 1 | `"01"` | Type A only |
| 4 | 2 | `"11"` | Type AB |
| 5 | 5 | `"10"` | Type B only |
We need to find the minimum cost for each $k$ from $1$ to $n$. For a given $k$, we want to select models such that at least $k$ models contribute to Feature A and at least $k$ models contribute to Feature B.
* **For $k=1$**:
To achieve $k=1$, we need at least one model for Feature A and at least one for Feature B. The minimum cost is $2$, achieved by selecting model $4$ (cost $2$, Type AB), which fulfills both requirements.
* **For $k=2$**:
To achieve $k=2$, we need at least two models for Feature A and two for Feature B. The minimum cost is $6$. One way to achieve this is by selecting model $4$ (cost $2$, Type AB), model $3$ (cost $1$, Type A only), and model $0$ (cost $3$, Type B only). The total cost is $2+1+3=6$. This set provides one A-suitable and one B-suitable model from model $4$, one A-suitable model from model $3$, and one B-suitable model from model $0$, totaling two A-suitable and two B-suitable models.
* **For $k=3$**:
For $k=3$, we need three models for Feature A and three for Feature B. The minimum cost is $15$. This can be achieved by selecting models $4$ (cost $2$, Type AB), $2$ (cost $9$, Type AB), $3$ (cost $1$, Type A only), and $0$ (cost $3$, Type B only). The total cost is $2+9+1+3=15$. This set provides two A-suitable and two B-suitable models from models $4$ and $2$, one A-suitable model from model $3$, and one B-suitable model from model $0$, totaling three A-suitable and three B-suitable models.
* **For $k=4$**:
For $k=4$, we need four models for Feature A and four for Feature B. The minimum cost is $26$. This requires using all models suitable for A or B: models $4, 2$ (Type AB), $3, 1$ (Type A only), and $0, 5$ (Type B only). The total cost is $2+9+1+6+3+5 = 26$. This set provides four A-suitable and four B-suitable models.
* **For $k=5, 6$**:
The maximum number of models that can contribute to Feature A is $4$ (two Type A only and two Type AB models). Similarly, for Feature B, it is also $4$ (two Type B only and two Type AB models). Since $k=5$ or $k=6$ requires more than $4$ suitable models for each feature, it is impossible to form a $k$-capable set, hence the cost is $-1$.
Loading problem statement...