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

543. Cafe
Time limit per test: 1 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



After competing in a programming contest n groups of friends have decided to take a rest from problem solving and have come to a cafe. The groups are numbered by integers from 1 to n, and the i-th group contains ai friends. The tables in the cafe are absolutely identical, for r persons each. Now the friends have faced a tricky problem. They want to sit at the tables in such a way that nobody sits alone separately from his or her group. In other words, for each person there should be another person from his/her group sitting at his/her table. There are no other restrictions. People from different groups can sit at the same table. Friends from the same group can sit at different tables. Places at the tables can be left vacant. Your task is to seat all the friends in the described way using the minimum possible number of tables.

Input
The first line of the input contains two integers n and r (1 ≤ n ≤ 2000; 3 ≤ r ≤ 2000), where n is the number of groups, and r is the number of places at each table. The second line contains n space-separated integers ai (2 ≤ ai ≤ 2000) — the number of people in the i-th group.

Output
Print the minimum possible number of tables to seat all the friends.

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

sample input
sample output
4 4
3 3 3 3
4



Note
A possible arrangement for the first sample test is:
table 1: 3 people from the 1st group, 1 empty place;
table 2: 2 people from the 1st group, 2 people from the 2nd group;
table 3: 4 people from the 2nd group;
table 4: 4 people from the 3rd group;
table 5: 3 people from the 3rd group, 1 empty place.

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

There are n groups of friends; group i has a[i] people. The cafe has identical tables with r seats each.

Seat everyone using the minimum number of tables, such that no one sits alone from their own group:
for every seated person, there must be at least one more person from the same group at the same table.

Groups may be split across multiple tables, and tables may mix people from different groups. Empty seats are allowed.

---

2) Key observations

1. Allowed table "chunks" per group have size ≥ 2.
   A group can split across tables, but every split part must have size at least 2.

2. It's enough to consider only chunks of size 2 and 3.
   Any integer k ≥ 2 can be represented as a sum of 2 and 3 (e.g., 4=2+2, 5=2+3, 6=3+3, …).
   So each group can be decomposed into some number of:
   - pairs (2-people chunks)
   - triples (3-people chunks)

3. For each group size x, the number of triples possible is restricted:
   - If x is even: triples can be 0,2,4,..., 2*(x//6)
   - If x is odd: must use at least one triple, then can add more by converting blocks of 6:
     triples can be 1,3,5,..., 1 + 2*((x-3)//6)

   Hence overall:
   - min_threes = number of odd groups (each needs ≥1 triple)
   - max_threes = sum of per-group maximum triples

   Also, the total number of triples must have the same parity as min_threes (changes come in steps of 2).

4. Binary search on the number of tables T works (monotonic feasibility):
   If you can seat everyone with T tables, you can also do it with T+1 tables (more capacity / more empties).

5. For fixed T, let:
   - S = sum(a[i])
   - E = T*r - S = number of empty seats available (must be >= 0)

   We try possible total triple counts threes and check if packing into tables is possible.

6. Packing logic depends on parity of r:
   - Even r: pairs fit naturally; triples cause parity issues, handled via:
     - each 6 seats can hold either 3+3 (two triples) or 2+2+2 (all pairs)
       => each 6-seat block "absorbs" 2 triples without needing empty seats.
     - leftover triples beyond absorption each typically needs one empty seat to fix parity.
   - Odd r: each table has odd capacity, so you generally need either:
     - at least one triple on the table, or
     - leave at least one seat empty on that table
     This creates two subcases in the feasibility check.

---

3) Full solution approach

Step A: Precompute triple bounds
Compute:
- S = sum(a)
- min_threes and max_threes as described above.

Step B: Binary search answer T
Search T in:
- low = ceil(S / r) (minimum tables by capacity)
- high = S (safe upper bound)

Use check(T) to decide if seating is possible with exactly T tables.

Step C: Feasibility check check(T)
1. Compute E = T*r - S. If E < 0 => impossible.
2. Iterate threes over all feasible totals:
   threes = min_threes, min_threes+2, ..., max_threes
   For each:
   - Remaining people after triples: S - 3*threes must be >= 0 and even (made of pairs).
3. Handle parity of r:

If r is odd:
- If threes < T:
  - At least T - threes tables would have no triple; each such table needs >=1 empty seat.
  - If E >= T - threes => feasible.
- Else (threes >= T):
  - Put 1 triple on every table (uses T triples), leaving per-table capacity r-3 which is even:
    - threes -= T, r' = r-3 (now even)
  - Continue like the even-r case with r'.

Now we are in an "even capacity" situation (r even or reduced to even):
- If E == 0 and threes is odd => impossible (parity can't be fixed).
- Absorb triples via 6-blocks:
  - absorbed = 2 * (r/6) * T
  - If threes <= absorbed => feasible
  - else threes -= absorbed, and remaining triples require empties:
    - if E >= threes => feasible

If any threes works => check(T)=true. Otherwise false.

Complexity
- Precomputation: O(n)
- Binary search: O(log S)
- Each check: loops over possible triple counts in steps of 2 (fast enough under constraints in intended solutions)

---

4) C++ implementation (with comments)

```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, r;
vector<int> a;

void read() {
    cin >> n >> r;
    a.resize(n);
    cin >> a;
}

bool check(
    int64_t tables, int64_t total_people, int64_t min_threes, int64_t max_threes
) {
    int64_t empty = tables * r - total_people;
    if(empty < 0) {
        return false;
    }

    for(int64_t threes = min_threes; threes <= max_threes; threes += 2) {
        int64_t remaining_seats = total_people - 3 * threes;
        if(remaining_seats < 0 || remaining_seats % 2 != 0) {
            continue;
        }

        int64_t cur_threes = threes;
        int64_t cur_r = r;

        if(cur_r % 2 == 1) {
            if(cur_threes < tables) {
                if(empty >= tables - cur_threes) {
                    return true;
                }
                continue;
            }
            cur_threes -= tables;
            cur_r -= 3;
        }

        if(empty == 0 && cur_threes % 2 == 1) {
            continue;
        }

        int64_t absorbed = 2 * (cur_r / 6) * tables;
        if(cur_threes <= absorbed) {
            return true;
        }

        cur_threes -= absorbed;

        if(empty >= cur_threes) {
            return true;
        }
    }

    return false;
}

void solve() {
    // There is some casework to be considered, but essentially we can think of
    // each group as some subsets of 2 or 3 people. If r was even, we should
    // prioritize making as many subsets of 2 people as possible, but if a[i] is
    // odd, we will have at least one subset of 3 people. If r >= 6, we can
    // potentially combine several 3-sized subsets together, while otherwise we
    // will just keep a single 3-size subset alone. After we figure out how to
    // distribute the 3-sized subsets, we can just use the 2-sized ones to fill
    // in the slacks. This heuristic works well for any even r by simply having
    // a single 3-sized subset for each odd a[i].
    //
    // When r is odd things become a bit trickier, since we might want to create
    // more odd-sized subgroups to avoid wasting one seat per table. Still, it
    // remains optimal to use only subgroups of size 2 and 3. For example with
    // r = 5 and groups {6, 4}, the best solution is to split the first group
    // into 3 + 3 and the second into 2 + 2, allowing us to seat everyone at
    // just two tables. This shows that sometimes splitting into more than one
    // 3-sized subset is beneficial, so we need a more general approach.
    //
    // To handle all cases correctly, we binary search on the number of tables M
    // and check whether it is possible to seat everyone with that many tables.
    // In the check function we first compute the total number of empty seats
    // across all tables. Then we try every possible number of 3-subgroups,
    // starting from the minimum required (one per odd group) and increasing by
    // two each time up to the maximum possible (since extra 3's usually come
    // in pairs when we break 6-person chunks). When the table size r is odd,
    // we handle two situations: if we don't have enough 3's to put at least one
    // in every table, we need at least one empty seat per table without a 3 to
    // avoid odd capacity issues. Otherwise we can place one 3 per table so the
    // remaining capacity becomes even. If there are no empty seats and an odd
    // number of leftover 3's, the configuration is invalid. Next we calculate
    // how many 3's can be fully absorbed in 6-seat blocks (two 3's or three 2's
    // per 6 seats) across all tables. If the leftover 3's can be absorbed this
    // way, we are done. Otherwise, each remaining 3 must be covered by one
    // empty seat to waste the odd seat safely. There are some details to get
    // right, but overall iterating through every possible 2/3 split is the core
    // idea.

    int64_t total_people = 0;
    int64_t min_threes = 0;
    int64_t max_threes = 0;

    for(int sz: a) {
        total_people += sz;
        if(sz % 2 == 0) {
            max_threes += 2 * (sz / 6);
        } else {
            min_threes++;
            max_threes += 1 + 2 * ((sz - 3) / 6);
        }
    }

    int64_t low = (total_people + r - 1) / r;
    int64_t high = total_people;
    int64_t ans = high;

    while(low <= high) {
        int64_t mid = (low + high) / 2;
        if(check(mid, total_people, min_threes, max_threes)) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }
    return 0;
}
```

---

5) Python implementation (with comments)

```python
import sys

def can_seat(T, n, r, total_people, min_threes, max_threes):
    """
    Return True if we can seat everyone using exactly T tables.
    We try all feasible counts of 3-sized subgroups (triples).
    """
    empty = T * r - total_people
    if empty < 0:
        return False

    # Try triple counts with correct parity: min_threes, min_threes+2, ...
    threes = min_threes
    while threes <= max_threes:
        remaining = total_people - 3 * threes

        # Remaining people must be representable by pairs => even and non-negative
        if remaining >= 0 and remaining % 2 == 0:
            cur_threes = threes
            cur_r = r

            # If r is odd, handle parity constraints per table
            if cur_r % 2 == 1:
                if cur_threes < T:
                    # Tables without a triple need 1 empty seat each
                    if empty >= (T - cur_threes):
                        return True
                    threes += 2
                    continue
                # Put one triple on every table so leftover capacity per table becomes even
                cur_threes -= T
                cur_r -= 3  # now even

            # Now cur_r is even
            if empty == 0 and (cur_threes % 2 == 1):
                threes += 2
                continue

            # Each 6 seats can contain two triples (3+3), absorbing 2 triples per 6-block
            absorbed = 2 * (cur_r // 6) * T
            if cur_threes <= absorbed:
                return True

            cur_threes -= absorbed

            # Each remaining triple requires one empty seat to "fix" parity/waste a seat
            if empty >= cur_threes:
                return True

        threes += 2

    return False


def solve():
    data = list(map(int, sys.stdin.read().strip().split()))
    n, r = data[0], data[1]
    a = data[2:2+n]

    total_people = sum(a)

    # Compute min/max possible number of triples overall
    min_threes = 0
    max_threes = 0
    for sz in a:
        if sz % 2 == 0:
            max_threes += 2 * (sz // 6)
        else:
            min_threes += 1
            max_threes += 1 + 2 * ((sz - 3) // 6)

    # Binary search for minimal feasible number of tables
    low = (total_people + r - 1) // r
    high = total_people
    ans = high

    while low <= high:
        mid = (low + high) // 2
        if can_seat(mid, n, r, total_people, min_threes, max_threes):
            ans = mid
            high = mid - 1
        else:
            low = mid + 1

    print(ans)


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