Вдоль дороги стоят *n* путешественников. Дорога представляет собой прямую, размерами путешественников можно пренебречь, считая их точками.

Водитель автобуса Василий, благодаря мобильному приложению, знает для каждого путешественника точку *x*<sub class="lower-index">*i*</sub>, в которой тот стоит. Кроме того, он знает расстояние *d*<sub class="lower-index">*i*</sub>, которое *i*-й путешественник хочет проехать на автобусе. Таким образом, *i*-й путешественник планирует выйти из автобуса в точке *x*<sub class="lower-index">*i*</sub> + *d*<sub class="lower-index">*i*</sub>. Теперь Василий хочет решить, кого из путешественников он подвезёт, а кого оставит пылиться у дороги.

Василий решил, что сегодня он должен хорошо заработать, поэтому решил перевезти в точности *a* путешественников. В автопарке есть автобусы любых видов. Чем больше мест в автобусе, тем дороже стоит его аренда.

Помогите Василию определить минимальное количество пассажирских мест в автобусе, которых будет достаточно для перевозки ровно *a* путешественников. Ни в какой момент времени в автобусе не может быть путешественников больше, чем количество пассажирских мест в автобусе. Василий сам может решить какое конкретно подмножество из *a* путешественников он перевезёт на автобусе.

Считайте, что автобус всегда едет слева направо (от меньших координат к большим) и начинает свой путь левее самого левостоящего путешественника. Если в одной точке какой-то путешественник должен выйти из автобуса, а другой войти, считайте, что сначала произойдет выход одного путешественника из автобуса, а затем другой путешественник сможет зайти в автобус.
В первой строке входных данных следует два целых положительных числа *n* и *a* (1 ≤ *a* ≤ *n* ≤ 200 000) — количество путешественников, стоящих вдоль дороги, и минимальное количество путешественников, которых Василий хочет подвезти.

В каждой из следующих *n* строк содержится по два целых числа *x*<sub class="lower-index">*i*</sub> и *d*<sub class="lower-index">*i*</sub> (1 ≤ *x*<sub class="lower-index">*i*</sub>, *d*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>) — координата, в которой находится *i*-й путешественник, а также расстояние, на которое он хочет переместиться на автобусе. Координаты путешественников заданы в произвольном порядке. В одной точке могут находиться несколько путешественников.
В первом тестовом примере достаточно одноместного автобуса. К примеру, Василий может подвезти третьего и первого путешественников, либо второго и первого путешественников.
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <fstream>

using namespace std;


int check(vector<vector<int>> const& get, int m)
{
    multiset<int> to_go;
    int ans = 0;
    for (auto i : get)
    {
        //cout << i[0] << ' ' << i[1] << ' ' << to_go.size() ' ' << to_go<< endl;
        while (to_go.size() > 0 && *to_go.begin() <= i[0])
        {
            //cout << *to_go.begin() << endl;
            to_go.erase(to_go.begin());
        }
        //cout << i[0] << ' ' << i[1] << ' ' << to_go.size() << endl;
        if (to_go.size() == m) {continue;}
        else
        {
            to_go.insert(i[0] + i[1]);
            ans++;
        }
    }
    return ans;
}

int main()
{
    //ifstream cin("bus.in");
    int n, a;
    cin >> n >> a;
    vector<vector<int>> get;
    for (int i = 0; i < n; i++)
    {
        int x, d;
        cin >> x >> d;
        get.push_back({x, d, i});
    }
    sort(get.begin(), get.end());
    int l = 0;
    int r = a;
    int m;
    while (r - l > 1)
    {
        m = l + (r - l) / 2;
        if (check(get, m) >= a)
        {
            r = m;
        }
        else
        {
            l = m;
        }
    }
    cout << r << endl;
    multiset<int> to_go;
    int ans = 0;
    for (auto i : get)
    {
        while (to_go.size() > 0 && *to_go.begin() <= i[0])
        {
            to_go.erase(to_go.begin());
        }
        if (to_go.size() == r) {continue;}
        else
        {
            to_go.insert(i[0] + i[1]);
            cout << i[2] + 1 << ' ';
            ans ++;
            if (a == ans)
            {break;}
        }
    }
    cout << endl;
    return 0;
}
