K. Тетрис: заданный порядок

Стакан шириной $W$ клеток. Сверху одна за другой падают $n$ фигурок в том порядке, в котором они перечислены во входных данных: $i$-я — горизонтальная полоска высотой в одну клетку и шириной $W_i$, её самая левая клетка имеет абсциссу $a_i$.

Фигурка падает, пока не ляжет на дно или хотя бы одной клеткой на уже упавшую фигурку. Выведите высоту получившейся конструкции.

Первая строка содержит числа $n$ и $W$ ($1 \le n \le 2 \cdot 10^4$, $1 \le W \le 1000$).

Следующие $n$ строк содержат по два числа $a_i$ и $W_i$ ($1 \le a_i \le W - W_i + 1$, $1 \le W_i \le W$).

Одно число — высота конструкции.