В новом мессенджере для учащихся Центра Помощи Магистрам, Кефтемерум, планируется обновление, в котором разработчики хотят оптимизировать набор сообщений, показываемых пользователю. Всего есть \(n\) сообщений, каждое сообщение характеризуется двумя целыми числами \(a_i\) и \(b_i\). Время, потраченное на прочтение набора сообщений с номерами \(p_1, p_2, \ldots, p_k\) (\(1 \le p_i \le n\), все \(p_i\) различны) рассчитывается по формуле:
\(\)\Large \sum_{i=1}^{k} a_{p_i} + \sum_{i=1}^{k - 1} |b_{p_i} - b_{p_{i+1}}|\(\)
Обратите внимание, что время прочтения набора сообщений, состоящего из одного сообщения с номером \(p_1\), равно \(a_{p_1}\). Также время прочтения пустого набора сообщений считается равным \(0\).
Пользователь может сам определить время \(l\), которое он готов провести в мессенджере. Мессенджер же должен сообщить пользователю максимально возможный размер набора сообщений, время прочтения которого не превышает \(l\). Обратите внимание, что максимальный размер набора сообщений может быть равен \(0\).
Разработчики популярного мессенджера не справились внедрить данную функцию, поэтому попросили вас решить эту задачу.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимально возможный размер набора сообщений, время прочтения которого не превышает \(l\).
Примечание
В первом наборе входных данных, можно взять набор из трёх сообщений с номерами \(p_1 = 3\), \(p_2 = 2\) и \(p_3 = 5\). Время, затрачиваемое на прочтение данного набора, равно \(a_3 + a_2 + a_5 + |b_3 - b_2| + |b_2 - b_5| = 2 + 1 + 2 + |4 - 5| + |5 - 3| = 8\).
Во втором наборе входных данных, можно взять набор из одного сообщения со номером \(p_1 = 1\). Время, затрачиваемое на прочтение данного набора, равно \(a_1 = 4\).
В пятом наборе входных данных можно показать, что не существует такого непустого набора сообщений, затрачиваемое время на прочтение которого не превышает \(l\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5 8
4 3
1 5
2 4
4 3
2 3
1 6
4 10
3 12
4 8
2 1
2 12
5 26
24 7
8 28
30 22
3 8
17 17
5 14
15 3
1000000000 998244353
179 239
228 1337
993 1007
|
3
1
2
1
0
|