<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

434. Chemists
Time limit per test: 0.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



The chemists had gathered to carry out an important experiment. That experiment required some tubes filled with liquid (each tube had to contain a certain amount of liquid). The experiment was set on 8 AM on the next day. They had worked hard, and there was the right amount of liquid in tubes by the end of the day. The chemists had decided to celebrate the occasion and, when morning came, they found out that someone had been pouring the liquid from and into the random tubes during the night. It is possible that this person had spilled the liquid or poured in an extra amount of it. Help the chemists to find out the minimum number of pourings to get the required amount of liquid in all tubes.

There are N tubes with Si liters of liquid in i-th tube. It is allowed to pour any amount of liquid from any one tube to another. You have to get the right amount of liquid in each tube (Di for i-th tube) after the minimum number of pourings.

Input
The first line of input contains an integer number N. The second line consists of N integer numbers Si separated by space. The third line consists of N integer numbers Di separated by space. 1 ≤ N ≤ 21, 1 ≤ Si, Di ≤ 1000.

Output
Output one number — the minimum number of pourings, or -1 if the pouring is impossible.

Example(s)
sample input
sample output
7
1 2 3 4 5 6 7
7 4 5 1 2 6 3
4

<|response|>
## 1) Abridged problem statement (concise)

You have **N (1…21)** tubes. Initially tube *i* contains **Sᵢ** liters, and you need to end with **Dᵢ** liters in each tube.  
One operation (“pouring”) transfers **any chosen amount** of liquid from **one tube to another**.

Find the **minimum number of pourings** needed to transform `S -> D`, or output **-1** if impossible.

---

## 2) Key observations

1. **Total volume must match**  
   A pouring only moves liquid between tubes, so the **sum of all amounts is invariant**.  
   If `sum(S) != sum(D)`, answer is **-1**.

2. **Work with differences**  
   Let  
   \[
   diff_i = S_i - D_i
   \]
   - `diff_i > 0`: tube *i* has extra liquid to send out  
   - `diff_i < 0`: tube *i* needs `-diff_i` liquid  
   - Over all tubes, `sum(diff) = 0` (if feasible).

3. **Zero-sum subsets can be fixed internally**  
   If a subset of tubes `G` satisfies  
   \[
   \sum_{i\in G} diff_i = 0
   \]
   then liquid can be redistributed **within G only** to reach all targets for tubes in `G`.

4. **A balanced group of size k needs ≤ (k − 1) pourings**  
   You can always fix a zero-sum group of `k` tubes using at most `k-1` transfers (think of sending required amounts along a spanning tree inside the group).

5. **Minimizing pourings ⇔ maximizing number of balanced groups**  
   If we partition all tubes into `g` disjoint zero-sum groups of sizes `k1..kg`, total pours:
   \[
   \sum (k_j - 1) = \left(\sum k_j\right) - g = N - g
   \]
   So we want to **maximize `g`**, the number of zero-sum groups in a partition of all tubes.

---

## 3) Full solution approach

### Step A: Check feasibility
- If `sum(S) != sum(D)`, print `-1`.

### Step B: Build `diff[]`
- `diff[i] = S[i] - D[i]`.

### Step C: Precompute subset sums
For each subset (bitmask) `mask` of tubes, compute:
\[
sum[mask] = \sum_{i \in mask} diff_i
\]
Do it in `O(2^N)` using the lowest-set-bit trick:
- `sum[mask] = sum[mask without lowbit] + diff[bit]`.

### Step D: DP over masks to maximize number of balanced groups
Define:
- `dp[mask]` = maximum number of zero-sum groups we can obtain from the tubes in `mask` (i.e., in some partition of `mask`).

Transition (classic trick used in the reference solution):
1. Inherit best from removing one element:
   \[
   dp[mask] = \max_{i \in mask} dp[mask \setminus \{i\}]
   \]
2. If the whole subset is balanced (`sum[mask]==0`), we can count it as one additional group:
   \[
   dp[mask] = dp[mask] + 1
   \]

Finally:
- `gmax = dp[(1<<N)-1]`
- answer = `N - gmax`

### Complexity
- Precompute sums: `O(2^N)`
- DP: `O(N * 2^N)`  
With `N ≤ 21`, this is feasible.

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> S(n), D(n);
    for (int i = 0; i < n; i++) cin >> S[i];
    for (int i = 0; i < n; i++) cin >> D[i];

    // 1) Feasibility check: total liquid is invariant under pourings
    long long sumS = 0, sumD = 0;
    for (int x : S) sumS += x;
    for (int x : D) sumD += x;
    if (sumS != sumD) {
        cout << -1 << "\n";
        return 0;
    }

    // 2) Build diff array: positive = extra, negative = deficit
    vector<int> diff(n);
    for (int i = 0; i < n; i++) diff[i] = S[i] - D[i];

    int Nmask = 1 << n;

    // 3) Precompute sum[mask] = sum(diff[i]) over i in mask
    vector<int> sum(Nmask, 0);
    for (int mask = 1; mask < Nmask; mask++) {
        int lb = mask & -mask;                // lowest set bit (as power of two)
        int bit = __builtin_ctz(lb);          // index of that bit
        sum[mask] = sum[mask ^ lb] + diff[bit];
    }

    // 4) dp[mask] = max number of balanced (sum==0) groups from subset mask
    vector<int> dp(Nmask, 0);
    for (int mask = 1; mask < Nmask; mask++) {

        // Option A: inherit best result from a smaller subset (remove one element)
        // This ensures dp[mask] becomes the best achievable within mask.
        int best = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                best = max(best, dp[mask ^ (1 << i)]);
            }
        }

        // Option B: if the entire mask is balanced, we can treat it as one group
        if (sum[mask] == 0) best += 1;

        dp[mask] = best;
    }

    int gmax = dp[Nmask - 1];      // maximum number of balanced groups
    int answer = n - gmax;         // min pourings = N - (#groups)

    cout << answer << "\n";
    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

def solve() -> None:
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)

    n = int(next(it))
    S = [int(next(it)) for _ in range(n)]
    D = [int(next(it)) for _ in range(n)]

    # 1) Total sum must match (pourings conserve total volume)
    if sum(S) != sum(D):
        print(-1)
        return

    # 2) Differences: positive = extra, negative = needs
    diff = [S[i] - D[i] for i in range(n)]

    size = 1 << n

    # 3) Precompute subset sums of diff in O(2^n)
    ssum = [0] * size
    for mask in range(1, size):
        lb = mask & -mask                 # lowest set bit
        bit = lb.bit_length() - 1         # index of that bit
        ssum[mask] = ssum[mask ^ lb] + diff[bit]

    # 4) dp[mask] = max number of balanced groups from subset mask
    dp = [0] * size
    for mask in range(1, size):
        best = 0

        # Inherit best from removing one element (iterate bits of mask)
        m = mask
        while m:
            lb = m & -m
            best = max(best, dp[mask ^ lb])
            m ^= lb

        # If this subset is balanced, count it as one group
        if ssum[mask] == 0:
            best += 1

        dp[mask] = best

    gmax = dp[size - 1]
    print(n - gmax)

if __name__ == "__main__":
    solve()
```

This produces the minimum number of pourings, and prints `-1` exactly when it’s impossible due to mismatched total liquid.