ポイントカード (Point Card) [第１６回日本情報オリンピック 予選（オンライン） B]

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_b

解説

https://atcoder.jp/contests/joi2017yo/submissions/8138857

N≦A[i]であれば、当たりとなり、当たりとなるようにM-1個選んでいく。
どれを当たりカードとすべきか考えたときになるべく、A[i]が大きいカードのほうが書き換える回数が少なくて済む。
よって、カードを考えるときにA[i]が大きいものから順に考えていくのが、最適であることがわかる。

A[i]を降順ソートしよう。
先頭からM-1個に対して、書き換える必要があれば書き換えて当たりカードにしていく。
必要な回数はN-A[i]であるが、もうすでに当たりの場合は負の数になる。
負の数の場合は0にしたいので、max(0, N - A[i])の総和を求めると答え。

int N, M, A[1010], B[1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) cin >> A[i] >> B[i];
    int ans = 0;
    sort(A, A + M, greater<int>());
    rep(i, 0, M - 1) ans += max(0, N - A[i]);
    cout << ans << endl;
}