<|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 (detailed comments)

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

int n, r;
vector<int> a;

/*
  Check if it is possible to seat everyone using exactly T tables.

  We represent every group as a collection of 2-chunks and 3-chunks.
  Let threes = total number of 3-chunks used across all groups.
  Then remaining people count is S - 3*threes and must be >=0 and even.

  We try all feasible threes from min_threes to max_threes (step 2).
*/
static bool check(long long T, long long S, long long min_threes, long long max_threes, int r) {
    long long E = T * 1LL * r - S; // total empty seats available
    if (E < 0) return false;

    // Try total number of triples with correct parity.
    for (long long threes = min_threes; threes <= max_threes; threes += 2) {
        long long rem = S - 3 * threes;
        // remaining must be nonnegative and even (composed of pairs)
        if (rem < 0 || (rem & 1)) continue;

        long long cur_threes = threes;
        int cur_r = r;

        // If table size is odd, handle the "odd capacity per table" constraint.
        if (cur_r & 1) {
            if (cur_threes < T) {
                // Not enough triples to put one on every table.
                // Any table without a triple must have an empty seat to make used seats even.
                if (E >= (T - cur_threes)) return true;
                continue;
            }
            // Put one triple on every table: remaining capacity per table becomes even.
            cur_threes -= T;
            cur_r -= 3; // now even
        }

        // Now cur_r is even.
        // If there are no empty seats, an odd number of triples can't be balanced.
        if (E == 0 && (cur_threes & 1)) continue;

        // In each 6 seats we can place either (3+3) or (2+2+2).
        // Thus each 6-seat block can "absorb" 2 triples without needing empties.
        long long absorbed = 2LL * (cur_r / 6) * T;

        if (cur_threes <= absorbed) return true;

        cur_threes -= absorbed;

        // Any leftover triple typically needs one empty seat to fix parity/mismatch.
        if (E >= cur_threes) return true;
    }

    return false;
}

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

    cin >> n >> r;
    a.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    long long S = 0;
    long long min_threes = 0, max_threes = 0;

    // Compute bounds on total number of triples possible.
    for (int x : a) {
        S += x;
        if (x % 2 == 0) {
            // even x: possible triples are 0,2,...,2*(x/6)
            max_threes += 2LL * (x / 6);
        } else {
            // odd x: must have at least one triple
            min_threes++;
            // max is 1 + 2*((x-3)/6)
            max_threes += 1LL + 2LL * ((x - 3) / 6);
        }
    }

    // Binary search minimum number of tables.
    long long low = (S + r - 1) / r; // at least enough seats
    long long high = S;              // safe upper bound
    long long ans = high;

    while (low <= high) {
        long long mid = (low + high) / 2;
        if (check(mid, S, min_threes, max_threes, r)) {
            ans = mid;
            high = mid - 1; // try fewer tables
        } else {
            low = mid + 1;  // need more tables
        }
    }

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

---

## 5) Python implementation (detailed comments)

```python
import sys

def can_seat(T: int, r: int, S: int, min_threes: int, max_threes: int) -> bool:
    """
    Return True if we can seat everyone using exactly T tables of size r.
    We try all feasible total counts of 3-chunks ("triples") from min_threes to max_threes, step 2.
    """
    E = T * r - S  # total empty seats
    if E < 0:
        return False

    threes = min_threes
    while threes <= max_threes:
        rem = S - 3 * threes
        # Remaining must be nonnegative and even (made from pairs).
        if rem >= 0 and rem % 2 == 0:
            cur_threes = threes
            cur_r = r

            # If table size is odd, we need either a triple or an empty seat per table.
            if cur_r % 2 == 1:
                if cur_threes < T:
                    # Tables without a triple require one empty seat.
                    if E >= (T - cur_threes):
                        return True
                    threes += 2
                    continue

                # Put one triple on each table, making remaining capacity even.
                cur_threes -= T
                cur_r -= 3  # now even

            # Now cur_r is even.
            # With no empty seats, odd number of triples can't be handled.
            if E == 0 and (cur_threes % 2 == 1):
                threes += 2
                continue

            # Each 6-seat block absorbs 2 triples (3+3).
            absorbed = 2 * (cur_r // 6) * T
            if cur_threes <= absorbed:
                return True

            cur_threes -= absorbed

            # Each leftover triple needs one empty seat to fix mismatch/parity.
            if E >= cur_threes:
                return True

        threes += 2

    return False


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

    S = sum(a)

    min_threes = 0
    max_threes = 0
    for x in a:
        if x % 2 == 0:
            max_threes += 2 * (x // 6)
        else:
            min_threes += 1
            max_threes += 1 + 2 * ((x - 3) // 6)

    low = (S + r - 1) // r
    high = S
    ans = high

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

    print(ans)


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

If you want, I can also add a small “sanity check” section explaining why the `6-seat absorption` rule is the right way to count how many triples can be placed without spending empty seats.