注意到

设集合$A$是选取DP的人员集合，$|A|=k$，总得分：

$$S=\sum_{i\in A}a_i+\sum_{i\notin A}b_i$$ $$\begin{align} S&=\sum_{i\in A}[b_i+(a_i-b_i)]+\sum_{i\notin A}b_i\\ &=\sum_{i=1}^n b_i+\sum_{i\in A}(a_i-b_i) \end{align}$$

$\displaystyle\sum_{i=1}^n b_i$是常数，因此

$$\max S \iff \max\sum_{i\in A}(a_i-b_i)$$

贪心：按$a_i-b_i$从大到小排序，选前$k$个进$A$。 反证：若最优解$A^*$不满足，

$$\exists\ x\in A^*,\ y\notin A^*,\quad a_x-b_x<a_y-b_y$$

令$A'=(A^*\setminus\{x\})\cup\{y\}$，

$$\Delta=\sum_{A'}-\sum_{A^*}=(a_y-b_y)-(a_x-b_x)>0$$

$\sum_{A'}>\sum_{A^*}$，矛盾。 $a_i-b_i$降序，前$k$取$a_i$，剩余取$b_i$最优。

C++

ll ans;
bool cmp(pll a,pll b)
{
    return (a.first-a.second)>(b.first-b.second);
}
void solve()
{
    ll n,m;
    ans=0;
    cin>>n>>m;
    vec<pll>a(n);
    for(int i=0;i<n;++i) cin>>a[i].first>>a[i].second;
    sort(a.begin(),a.end(),cmp);
    for(int i=0;i<n;++i)
    {
        if(i<m) ans+=a[i].first;
        else ans+=a[i].second;
    }
    cout<<ans<<'\n';
}
int main()
{
    AC;
    int t; cin>>t;
    while(t--) solve();
    return 0;
}

Python

import sys
def main():
    d=list(map(int,sys.stdin.read().split()))
    p=0
    t=d[p]
    p+=1
    for _ in range(t):
        n,m=d[p],d[p+1]
        p+=2
        a=[]
        for __ in range(n):
            x=d[p]
            y=d[p+1]
            a.append((x,y))
            p+=2
        a.sort(key=lambda x:x[0]-x[1],reverse=True)
        s=0
        for i in range(n):
            if i<m:
                s+=a[i][0]
            else:
                s+=a[i][1]
        print(s)
if __name__=="__main__":main()