AT_abc269_g [ABC269G] Reversible Cards 2

[problemUrl]: https://atcoder.jp/contests/abc269/tasks/abc269_g $ 1 $ から $ N $ までの番号がついた $ N $ 枚のカードがあります。 カード $ i $ の表には整数 $ A_i $, 裏には整数 $ B_i $ が書いてあります。 また、$ \sum_{i=1}^N\ (A_i\ +\ B_i)\ =\ M $ です。 $ k=0,1,2,...,M $ について次の問題を解いてください。 > $ N $ 枚のカードがすべて表側が見える状態で並べられています。あなたは $ 0 $ 枚以上 $ N $ 枚以下のカードを選び、それらを裏返すことができます。 > 見えている数の和が $ k $ になるには最小で何枚のカードを裏返す必要がありますか？枚数を出力してください。 > ただし、どのようにカードを裏返しても見えている数の和が $ k $ にならない場合は $ -1 $ を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_N $ $ B_N $

$ M+1 $ 行出力せよ。$ i $ 行目には $ k=i-1 $ のときの答えを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 0\ \leq\ M\ \leq\ 2\ \times\ 10^5 $ - $ 0\ \leq\ A_i,\ B_i\ \leq\ M $ - $ \sum_{i=1}^N\ (A_i\ +\ B_i)\ =\ M $ - 入力される値はすべて整数 ### Sample Explanation 1 例えば $ k=0 $ のときは、カード $ 2 $ のみを裏返せば見えている数の和を $ 0+0+0=0 $ にすることができて、これが最適です。 また、$ k=5 $ のときは、すべてのカードを裏返せば見えている数の和を $ 2+0+3=5 $ にすることができて、これが最適です。