Tras prevenir con éxito la extinción de los gatos durante la celebración anual del Día Nacional del Gato (NCD), el gato Ket ha recibido quejas por hambre del reino de los gatos caníbales. Por lo tanto, se le ha encomendado a Ket la tarea de entregar comida para evitar que vuelvan a recurrir al canibalismo.
Este reino gatuno puede modelarse como un camino muy largo que va de oeste a este. Hay un banco de comida en el extremo oeste del camino. Hay $n$ casas de gatos al este del banco de comida, numeradas del 1 al $n$. Se garantiza que $n$ es par. La primera casa está a $d[1]$ kilómetros al este del banco de comida. Para $i \geq 2$, la $i$-ésima casa está a $d[i]$ kilómetros al este de la $(i-1)$-ésima casa.
Ket conducirá un camión de reparto para entregar comida a las casas. El camión comienza en el banco de comida e inicialmente tiene $x$ unidades de combustible. 1 unidad de combustible permite a Ket conducir su camión 1 kilómetro a lo largo del camino.
La $i$-ésima casa tiene $f[i]$ unidades de combustible para que el camión las use. El camión tiene almacenamiento de combustible infinito y solo se detiene cuando se queda sin combustible. El camión no necesita regresar al banco de comida después de salir.
Figura 1. Representación del camino con el banco de comida y las casas de los gatos.
Además, Ket tiene una varita mágica. Con un movimiento de su varita, puede intercambiar la cantidad de combustible almacenada en la $i$-ésima y la $(n - i + 1)$-ésima casa de los gatos. Este intercambio solo puede realizarse si el combustible en ambas casas aún no se ha utilizado. Ayuda a Ket a encontrar el índice de la casa más lejana $D$ a la que puede llegar, utilizando cualquier número de intercambios. Además, ayuda a Ket a encontrar el número mínimo de intercambios $S$ necesarios para llegar a la casa $D$.
Entrada
Tu programa debe leer desde la entrada estándar.
La primera línea de la entrada contiene dos enteros separados por espacios $n$ y $x$.
La segunda línea de la entrada contiene $n$ enteros separados por espacios $d[1], d[2], \dots, d[n]$.
La tercera línea de la entrada contiene $n$ enteros separados por espacios $f[1], f[2], \dots, f[n]$.
Salida
Tu programa debe imprimir a la salida estándar.
Imprime dos enteros separados por espacios en una sola línea. El primer entero debe ser $D$, el índice de la casa más lejana a la que Ket puede llegar, seguido de $S$, el número mínimo de intercambios necesarios para llegar a la casa $D$.
Subtareas
Para todos los casos de prueba, la entrada cumplirá con los siguientes límites:
- $2 \leq n \leq 500\,000$
- $n$ es par.
- $1 \leq d[i] \leq 10^9$ para todo $1 \leq i \leq n$
- $1 \leq f[i] \leq 10^9$ para todo $1 \leq i \leq n$
- $d[1] \leq x \leq 10^9$
Tu programa será probado en instancias de entrada que satisfagan las siguientes restricciones:
| Subtarea | Puntuación | Restricciones adicionales | ||
|---|---|---|---|---|
| 0 | 0 | Casos de prueba de ejemplo | ||
| 1 | 7 | $ | f[i] - f[n - i + 1] | = k$ para alguna constante $k$, para todo $1 \leq i \leq n$ |
| 2 | 12 | $n \leq 40$ | ||
| 3 | 14 | $f$ es no decreciente ($f[i] \leq f[i + 1]$ para todo $1 \leq i \leq n - 1$) | ||
| 4 | 19 | $D \leq \frac{n}{2}$ | ||
| 5 | 21 | $n \leq 5000$ | ||
| 6 | 27 | Sin restricciones adicionales |
Nota: El valor absoluto de un número $x$, denotado $|x|$, es el número no negativo igual a la distancia entre 0 y $x$ en una recta numérica. Por ejemplo, $|5| = 5$ y $|-5| = 5$.
Ejemplos
Entrada 1
6 1 1 1 3 1 1 6 1 1 1 4 3 2
Salida 1
5 1
Nota
Hay un banco de comida con $n = 6$ casas a su este. El camión de Ket comienza con $x = 1$ unidad de combustible y se mueve a la casa 1. Luego reposta en la casa 1 y conduce a la casa 2. En este punto, es óptimo para Ket usar su varita mágica para intercambiar las cantidades de combustible en las casas 2 y 5, lo que le permite repostar 3 unidades de combustible y llegar a la casa 3. Posteriormente, puede repostar 1 unidad de combustible antes de viajar a las siguientes dos casas, repostando 4 y 1 unidades (debido al intercambio anterior) de combustible en las casas 4 y 5 respectivamente. Luego le quedarán 4 unidades de combustible, lo que le dejará incapaz de viajar a la casa 6 ya que requiere 6 unidades de combustible. Dado que Ket se queda sin combustible antes de llegar a la casa 6, solo puede viajar a la casa 5. Además, tuvo que hacer un intercambio con su varita mágica. Por lo tanto, $D = 5$ y $S = 1$.
Entrada 2
6 5 3 8 3 1 4 1 2 7 1 6 2 7
Salida 2
6 1
Entrada 3
6 2 2 24 25 40 5 11 4 12 14 16 20 30
Salida 3
3 2
Entrada 4
6 10 3 6 3 7 8 6 4 3 1 7 1 6
Salida 4
5 1