p543.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;
}

=================
p543.ans2
======================
4

=================
p543.in1
======================
3 4
5 6 7

=================
p543.ans1
======================
5

=================
p543.in2
======================
4 4
3 3 3 3

=================
statement.txt
======================
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.

=================
