In this case any $$$a[i] \gt =b[i]$$$ for all $$$(1 \lt =i \lt =n)$$$, you can easily make a[i]%b[i]==0 by decreasing the value of a[i] or increase the value of b[i] with cost 0, and for this conditon b[i]>a[i] only the cost is 1.

#include <bits/stdc++.h>
 
using namespace std;
 
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define testcase int t; cin>>t; for(int i=0;i<t;i++)
 
#define ll long long int
ll lcm(ll a, ll b) {
    return (a / __gcd(a, b)) * b;
}
 
 
void solved(){
	/*start*/
    ll n;
    cin>>n;
    vector <ll> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    vector <ll> b(n);
    for(int i=0;i<n;i++){
        cin>>b[i];
    }
    ll cnt=0;
    for(int i=0;i<n;i++){
        if(a[i]<b[i]){
            cnt+=(b[i]-a[i]);
        }
    }
    cout<<cnt<<"\n";
	/*end*/
}
 
int main(){
	faster
	testcase 
	solved();
}

In this, to minimise the number of string h, we will count the character that is extra from s, then we can make exactly (extra_char_left_count+k-1)/k;

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
	ll t;
	cin>>t;
	while(t--){
	    ll n,m,k;
	    cin>>n>>m>>k;
	    string s,p;
	    cin>>s>>p;
	    int l=0,i=0;
	    while(l<m&&i<n){
	        if(s[i]==p[l]){
	            l++;
	        }
	        i++;
	    }
	    if(l==m){
	        cout<<(n-m+k-1)/k<<"\n";
	    }
	    else{
	        cout<<"-1\n";
	    }
	}
	
}

Inside each group, if the most frequent value $$$mx$$$ is less than or equal to half the group size $$$sz$$$, you can pair almost everyone. If $$$mx \gt sz/2$$$, you are forced to have $$$sz - 2(sz - mx)$$$ leftovers of that specific value. Globally, the same principle applies: the maximum inter-group pairs you can form is limited by the "gap" between the total leftovers and the most dominant leftover value.

The total answer is the sum of local pairs plus these budgeted global pairs. This ensures you only "buy" matches that are physically possible to form given the leftover value constraints.

#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#endif
#define int long long
#define pii pair<int, int>
const int INF = 1e18;
const int MOD = 1e9 + 7;
 
void solve() {
    int n , k , c;
   cin >> n >> k >> c;
 
    vector<int> a(n) , b(n);
    for (int i=0;i<n;i++) {
        cin >> a[i];
    }
 
    for (int i=0;i<n;i++) {
        cin >> b[i];
    }
 
    map<int, map<int, int>> m;
    for (int i=0;i<n;i++) {
        m[b[i]][a[i]]++;
    }
 
    int ans = 0;
    int tot = 0;
    int g_mx = 0;
    map<int, int> rem;
 
    for (auto it : m) {
        map<int, int> &group = it.second;
        
        int sz = 0;
        int mx = 0;
        int dom = -1;
 
        for (auto c_it : group) {
            int cnt = c_it.second;
            int cl = c_it.first;
            sz += cnt;
            if (cnt > mx) {
                mx = cnt;
                dom = cl;
            }
        }
 
        if (mx > sz / 2) {
            int p = sz - mx;
            ans += p;
            int r = sz - (2 * p);
            rem[dom] += r;
            tot += r;
        } 
        else {
            ans += sz / 2;
            if (sz % 2 != 0) {
                tot += 1;
            }
        }
    }
 
    for (auto r_it : rem) {
        if (r_it.second > g_mx) {
            g_mx = r_it.second;
        }
    }
 
    int can_p = tot / 2;
    if (tot - g_mx < can_p) {
        can_p = tot - g_mx;
    }
 
    int bud_p = (c / k) * 2;
 
    int paid = can_p;
    if (bud_p < paid) {
        paid = bud_p;
    }
 
    cout << ans + paid << '\n';
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
 
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
const ll MOD = 957483783;
const int MAXB = 41;   
 
ll dp[MAXB][2];
int bitsX[MAXB], bitsB[MAXB];
 
ll dfs(int pos, bool tight) {
    if (pos == MAXB) return 1;
 
    if (!tight && dp[pos][0] != -1)
        return dp[pos][0];
 
    ll res = 0;
    int limit = tight ? bitsX[pos] : 1;
 
    for (int b = 0; b <= limit; b++) {
        if (bitsB[pos] && b == 0) continue;
        res += dfs(pos + 1, tight && (b == limit));
    }
 
    if (!tight)
        dp[pos][0] = res;
 
    return res;
}
 
ll countUpTo(ll X, ll B) {
    if (X < 0) return 0;
 
    for (int i = 0; i < MAXB; i++) {
        bitsX[i] = (X >> (MAXB - 1 - i)) & 1;
        bitsB[i] = (B >> (MAXB - 1 - i)) & 1;
    }
 
    memset(dp, -1, sizeof(dp));
    return dfs(0, 1);
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
 
    while (T--) {
        ll L, R, K;
        cin >> L >> R >> K;
 
        ll ans = 0;
 
        vector<ll> candidates;
        candidates.push_back(K);
 
        // Generate prefix-supermasks (only 0..40 bits)
        for (int i = MAXB - 1; i >= 0; i--) {
            if (!(K & (1LL << i))) {
                ll B = K;
                B |= (1LL << i);
                B &= ~((1LL << i) - 1);
                if (B >= K)
                    candidates.push_back(B);
            }
        }
 
        for (ll B : candidates) {
            ll cnt = countUpTo(R, B) - countUpTo(L - 1, B);
            ans = max(ans, cnt);
        }
 
        cout << (ans % MOD) << "\n";
    }
 
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define endl "\n"
 
int mod;
 
int ma(int a, int b) {return (a%mod + b%mod + mod) % mod;}
int ms(int a, int b) {return (a%mod - b%mod + mod) % mod;}
int mm(int a, int b) {return (a%mod * b%mod) % mod;}
 
int modexp(int base, int exp) {
    int res = 1;
    base %= mod;
    while(exp) {
        if(exp & 1) res = mm(res, base);
        base = mm(base, base);
        exp >>= 1;
    }
    return res;
}
 
int modinv(int x) {
    return modexp(x, mod-2);
}
 
void solve()
{
    int q;
    cin >> mod >> q;
 
    // Precompute factorials only up to mod-1
    vector<int> fact(mod), invfact(mod);
 
    fact[0] = 1;
    for(int i = 1; i < mod; i++)
        fact[i] = mm(fact[i-1], i);
 
    invfact[mod-1] = modinv(fact[mod-1]);
    for(int i = mod-2; i >= 0; i--)
        invfact[i] = mm(invfact[i+1], i+1);
 
    auto comb = [&](int n, int r) -> int {
        if(n < 0 || r < 0 || r > n) return 0;
        return mm(fact[n], mm(invfact[n-r], invfact[r]));
    };
 
    auto lucas = [&](int n, int r) -> int {
        int ans = 1;
        while(n > 0 || r > 0) {
            ans = mm(ans, comb(n % mod, r % mod));
            n /= mod;
            r /= mod;
        }
        return ans;
    };
 
    while(q--) {
        int k,l,r;
        cin >> k >> l >> r;
 
        int right = lucas(r + k + 1, k + 2);
        int left  = lucas(l + k, k + 2);
 
        cout << ms(right, left) << endl;
    }
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    solve();
}

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define endl "\n"
 
bool TestCases = false;
int inf = 1e18;
 
bool check(int i,int n) {
    if(i==1) return true;
    int l = 2;
    int r = 1e9;
    while(l<=r) {
        int m = (l+r)/2;
        int t = 1;
        bool ok = true;
        for(int j=1;j<=i;j++) {
            if(t>inf/m) {
                ok = false; break;
            }
            t*=m;
            if(t>n) {
                ok = false; break;
            }
        }
        if(!ok) {
            r = m-1;
        }else if(t==n) {
            return true;
        }else {
            l = m+1;
        }
    }
    return false;
}
 
void solve()
{
    int n; cin>>n;
    for(int i=60;i>0;i--) {
        if(check(i,n)) {
            cout<<i;
            return;
        }
    }
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int t = 1;
    if(TestCases)
    {
        cin >> t;
    }
 
    while(t--)
    {
        solve();
    }
}

#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#include <C:/Users/ajiit/Desktop/Future/Coding/Problem Solving/debug.cpp>
#endif
#define int long long
#define pii pair<int, int>
const int INF = 1e18;
const int MOD = 1e9 + 7;
const int MAXN = 1000005;
 
vector<int> divs[MAXN];
int memo[MAXN];
 
void pre() {
    for (int i = 1; i < MAXN; ++i) {
        for (int j = 2 * i; j < MAXN; j += i) {
            divs[j].push_back(i);
        }
    }
    memset(memo, -1, sizeof(memo));
}
 
int get_grundy(int u) {
    if (memo[u] != -1) return memo[u];
    
    int mask = 0;
    for (int v : divs[u]) {
        if (u % 2 != 0) {
            mask |= (1LL << get_grundy(v));
        } else {
            if (v % 2 == 0) {
                mask |= (1LL << get_grundy(v));
            }
        }
    }
    
    int g = 0;
    while ((mask >> g) & 1) g++;
    return memo[u] = g;
}
 
void solve() {
    int n;
    cin >> n;
 
    vector<int> a(n);
    int par = 0;
    int xr = 0;
    
    for (int i=0;i<n;i++) {
        cin >> a[i];
        par = (par + a[i]) % 2;
        xr ^= get_grundy(a[i]);
    }
 
    if (par == 0) {
        if (xr > 0) cout << "Alice\n";
        else cout << "Bob\n";
    } 
    else {
        bool ok = false;
        for (int x : a) {
            if (x % 2 == 0) {
                int target = xr ^ get_grundy(x);
                for (int v : divs[x]) {
                    if (v % 2 != 0) {
                        if (get_grundy(v) == target) {
                            ok = true;
                            break;
                        }
                    }
                }
            }
            if (ok) break;
        }
 
        if (ok) cout << "Alice\n";
        else cout << "Bob\n";
    }
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    pre();
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
 
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define FOR(i,a,b) for(int i=a; i<b; i++)
using vi=vector<int>;
using vii=vector<vi>;
using vpii=vector<pair<int,int>>;
#define pb push_back
 
int quer(int u, int v) {
    cout<<"? "<<u<<" "<<v<<endl;
    int ans; cin>>ans;
    if (ans==-1) exit(0);
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin>>n;
    vi st; vpii diag;
    st.pb(1); st.pb(2);
    FOR(i,3,n+1) {
        while (st.size()>=2) {
            int top=st.back();
            int pv=st[st.size()-2];
            int cut=0;
            if (pv==1 && i==n) {
              cut=0;
            }
            else {
                cut=quer(pv,i);
            }
            if (cut==0){
                if (!(pv==1 && i==n)){
                    diag.pb({pv,i});
                }
                st.pop_back();
            }
            else {
                break;
            }
        }
        st.pb(i);
    }
    cout<<"!"<<endl;
    FOR(i,0,size(diag)) {
        cout<<diag[i].first<<" "<<diag[i].second<<endl;
    }
    cout<<flush;
}