После успешного предотвращения вымирания кошек во время ежегодного празднования Национального дня кошек (NCD), кот Кет получил жалобы на голод от королевства кошек-каннибалов. Поэтому Кету было поручено доставить еду, чтобы предотвратить их возвращение к каннибализму.
Это кошачье королевство можно представить как очень длинную дорогу, идущую с запада на восток. На западном конце дороги находится продовольственный склад. К востоку от склада расположены $n$ кошачьих домов, пронумерованных от 1 до $n$. Гарантируется, что $n$ — четное число. Первый дом находится на расстоянии $d[1]$ километров к востоку от продовольственного склада. Для $i \ge 2$ $i$-й дом находится на расстоянии $d[i]$ километров к востоку от $(i-1)$-го дома.
Кет будет управлять грузовиком для доставки еды в дома. Грузовик начинает путь от продовольственного склада и изначально имеет $x$ единиц топлива. 1 единица топлива позволяет Кету проехать на грузовике 1 километр по дороге.
В $i$-м доме есть $f[i]$ единиц топлива для использования грузовиком. Грузовик имеет бесконечный объем топливного бака и останавливается только тогда, когда у него заканчивается топливо. Грузовику не нужно возвращаться на продовольственный склад после отправления.
Схема расположения продовольственного склада и кошачьих домов
Кроме того, у Кета есть волшебная палочка. Одним взмахом палочки он может поменять местами количество топлива, хранящееся в $i$-м и $(n - i + 1)$-м кошачьих домах. Этот обмен может произойти только в том случае, если топливо в обоих домах еще не было использовано. Помогите Кету найти индекс самого дальнего дома $D$, до которого он может добраться, используя любое количество обменов. Также помогите Кету найти минимальное количество обменов $S$, необходимое для того, чтобы добраться до дома $D$.
Входные данные
Ваша программа должна считывать данные из стандартного потока ввода.
Первая строка входных данных содержит два целых числа $n$ и $x$, разделенных пробелом.
Вторая строка входных данных содержит $n$ целых чисел $d[1], d[2], \dots, d[n]$, разделенных пробелами.
Третья строка входных данных содержит $n$ целых чисел $f[1], f[2], \dots, f[n]$, разделенных пробелами.
Выходные данные
Ваша программа должна выводить данные в стандартный поток вывода.
Выведите два целых числа, разделенных пробелом, на одной строке. Первое число должно быть $D$ — индекс самого дальнего дома, до которого может добраться Кет, а второе — $S$ — минимальное количество обменов, необходимое для того, чтобы добраться до дома $D$.
Подзадачи
Для всех тестовых случаев входные данные будут удовлетворять следующим ограничениям:
- $2 \le n \le 500\,000$
- $n$ — четное число.
- $1 \le d[i] \le 10^9$ для всех $1 \le i \le n$
- $1 \le f[i] \le 10^9$ для всех $1 \le i \le n$
- $d[1] \le x \le 10^9$
Ваша программа будет протестирована на входных данных, удовлетворяющих следующим ограничениям:
| Подзадача | Баллы | Дополнительные ограничения | ||
|---|---|---|---|---|
| 0 | 0 | Примеры тестов | ||
| 1 | 7 | $ | f[i] - f[n - i + 1] | = k$ для некоторой константы $k$, для всех $1 \le i \le n$ |
| 2 | 12 | $n \le 40$ | ||
| 3 | 14 | $f$ не убывает ($f[i] \le f[i + 1]$ для всех $1 \le i \le n - 1$) | ||
| 4 | 19 | $D \le \frac{n}{2}$ | ||
| 5 | 21 | $n \le 5000$ | ||
| 6 | 27 | Нет дополнительных ограничений |
Примечание
Абсолютная величина числа $x$, обозначаемая $|x|$, — это неотрицательное число, равное расстоянию между 0 и $x$ на числовой прямой. Например, $|5| = 5$ и $|-5| = 5$.
Примеры
Входные данные 1
6 1 1 1 3 1 1 6 1 1 1 4 3 2
Выходные данные 1
5 1
Примечание
Существует продовольственный склад с $n = 6$ домами к востоку от него. Грузовик Кета начинает путь с $x = 1$ единицей топлива и доезжает до дома 1. Затем он заправляется в доме 1 и едет к дому 2. В этот момент для Кета оптимально использовать волшебную палочку, чтобы поменять местами количество топлива в домах 2 и 5, что позволяет ему дозаправиться на 3 единицы топлива и доехать до дома 3. Впоследствии он может дозаправиться на 1 единицу топлива перед поездкой к следующим двум домам, дозаправившись на 4 и 1 единицу (из-за предыдущего обмена) топлива в домах 4 и 5 соответственно.
После этого у него останется 4 единицы топлива, чего недостаточно для поездки к дому 6, так как для этого требуется 6 единиц топлива. Поскольку у Кета заканчивается топливо до того, как он добирается до дома 6, он может доехать только до дома 5. Кроме того, ему пришлось совершить один обмен волшебной палочкой. Таким образом, $D = 5$ и $S = 1$.
Входные данные 2
6 5 3 8 3 1 4 1 2 7 1 6 2 7
Выходные данные 2
6 1
Входные данные 3
6 2 2 24 25 40 5 11 4 12 14 16 20 30
Выходные данные 3
3 2
Входные данные 4
6 10 3 6 3 7 8 6 4 3 1 7 1 6
Выходные данные 4
5 1