<|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

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<int> S, D;

void read() {
    cin >> n;
    S.resize(n);
    D.resize(n);
    cin >> S >> D;
}

void solve() {
    // It's clear that it's impossible when the sum of S and D are different. We
    // can further generalize this argument. Consider a set of positions
    // i[1], ..., i[k] with sum of S and D being equal - we can always make the
    // values equal in k - 1 steps. Unless there are some equal values, or more
    // generally another subset that has equal sum between S and D, we can't do
    // better than k - 1 steps. We can prove this because if there is no
    // subset of equal sum, we would have to have a direct or indirect
    // "connection" between each of the elements in the subset. Trivially to
    // have something connected, we need at least k - 1 edges (number of edges
    // in a spanning tree).
    //
    // This intuition leads us to the idea that we want to split the N elements
    // into the largest number subsets of equal sum between S and D. For
    // simplicity, we could instead look at the difference between S and D as
    // then we are interested in sum / balance equal to 0. To do this, we could
    // do a bitmask dp[mask][sum_subset_so_far]. Alternatively, we could do a
    // 3^n approach. However, this might still be a bit too slow and instead we
    // can notice the other main observations - consider some arbitrary order
    // p[1], ..., p[n] of elements we will consider. Let's also do pref[i],
    // being the prefix sum over this order. We have the incentive to do 0-sum
    // subsets as often as possible, meaning that whenever the prefix sum
    // reaches 0, we should always snap a new group. Particularly, if a 0-group
    // starts at p[l] and ends at p[r], then it's sum is psum[r] - psum[l - 1],
    // but we know that psum[l - 1] = 0 (because the prefix until l - 1 is
    // decomposed into 0-sum segments).
    //
    // To summarize, this means that we don't actually need to keep the second
    // dimension of the DP - we can always just consider the sum of D and S in
    // the current mask, and "subtract one" every time it reaches 0.

    if(accumulate(S.begin(), S.end(), 0) != accumulate(D.begin(), D.end(), 0)) {
        cout << -1 << endl;
        return;
    }

    vector<int> diff(n);
    for(int i = 0; i < n; i++) {
        diff[i] = S[i] - D[i];
    }

    vector<int> sum((1 << n), 0);
    for(int mask = 1; mask < (1 << n); mask++) {
        int lb = mask & (-mask);
        int bit = __builtin_ctz(lb);
        sum[mask] = sum[mask ^ lb] + diff[bit];
    }

    vector<int> dp((1 << n), 0);
    for(int mask = 1; mask < (1 << n); mask++) {
        for(int i = 0; i < n; i++) {
            if(mask & (1 << i)) {
                dp[mask] = max(dp[mask], dp[mask ^ (1 << i)]);
            }
        }
        if(sum[mask] == 0) {
            dp[mask]++;
        }
    }

    cout << n - dp[(1 << n) - 1] << endl;
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    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.
