Après avoir réussi à empêcher l'extinction des chats lors de la célébration annuelle de la Journée Nationale du Chat (NCD), le chat Ket a reçu des plaintes concernant la faim de la part du royaume des chats cannibales. Par conséquent, Ket a été chargé de livrer de la nourriture pour les empêcher de recourir à nouveau au cannibalisme.
Ce royaume félin peut être modélisé comme une très longue route allant de l'ouest vers l'est. Il y a une banque alimentaire à l'extrémité ouest de la route. Il y a $n$ maisons de chats à l'est de la banque alimentaire, numérotées de 1 à $n$. Il est garanti que $n$ est pair. La première maison est située à $d[1]$ kilomètres à l'est de la banque alimentaire. Pour $i \geq 2$, la $i$-ième maison est située à $d[i]$ kilomètres à l'est de la $(i - 1)$-ième maison.
Ket conduira un camion de livraison pour distribuer de la nourriture aux maisons. Le camion part de la banque alimentaire et dispose initialement de $x$ unités de carburant. 1 unité de carburant permet à Ket de conduire son camion sur 1 kilomètre le long de la route.
La $i$-ième maison dispose de $f[i]$ unités de carburant que le camion peut utiliser. Le camion possède une capacité de stockage de carburant infinie et ne s'arrête que lorsqu'il tombe en panne de carburant. Le camion n'a pas besoin de retourner à la banque alimentaire après son départ.
En plus, Ket possède une baguette magique. D'un coup de baguette, il peut échanger la quantité de carburant stockée dans la $i$-ième maison et dans la $(n - i + 1)$-ième maison. Cet échange ne peut avoir lieu que si le carburant dans les deux maisons n'a pas encore été utilisé. Aidez Ket à trouver l'indice de la maison la plus éloignée $D$ qu'il peut atteindre, en utilisant n'importe quel nombre d'échanges. Aidez également Ket à trouver le nombre minimum d'échanges $S$ requis pour atteindre la maison $D$.
Entrée
Votre programme doit lire depuis l'entrée standard.
La première ligne de l'entrée contient deux entiers séparés par des espaces $n$ et $x$.
La deuxième ligne de l'entrée contient $n$ entiers séparés par des espaces $d[1], d[2], \dots, d[n]$.
La troisième ligne de l'entrée contient $n$ entiers séparés par des espaces $f[1], f[2], \dots, f[n]$.
Sortie
Votre programme doit imprimer sur la sortie standard.
Affichez deux entiers séparés par un espace sur une seule ligne. Le premier entier doit être $D$, l'indice de la maison la plus éloignée que Ket peut atteindre, suivi de $S$, le nombre minimum d'échanges requis pour atteindre la maison $D$.
Contraintes
Pour tous les cas de test, l'entrée satisfera les limites suivantes :
- $2 \leq n \leq 500\,000$
- $n$ est pair.
- $1 \leq d[i] \leq 10^9$ pour tout $1 \leq i \leq n$
- $1 \leq f[i] \leq 10^9$ pour tout $1 \leq i \leq n$
- $d[1] \leq x \leq 10^9$
Votre programme sera testé sur des instances d'entrée qui satisfont les restrictions suivantes :
| Sous-tâche | Score | Contraintes supplémentaires | ||
|---|---|---|---|---|
| 0 | 0 | Exemples de test | ||
| 1 | 7 | $ | f[i] - f[n - i + 1] | = k$ pour une constante $k$, pour tout $1 \leq i \leq n$ |
| 2 | 12 | $n \leq 40$ | ||
| 3 | 14 | $f$ est non-décroissante ($f[i] \leq f[i + 1]$ pour tout $1 \leq i \leq n - 1$) | ||
| 4 | 19 | $D \leq \frac{n}{2}$ | ||
| 5 | 21 | $n \leq 5000$ | ||
| 6 | 27 | Aucune contrainte supplémentaire |
Note : La valeur absolue d'un nombre $x$, notée $|x|$, est le nombre non négatif égal à la distance entre 0 et $x$ sur une droite numérique. Par exemple, $|5| = 5$ et $|-5| = 5$.
Exemples
Entrée 1
6 1 1 1 3 1 1 6 1 1 1 4 3 2
Sortie 1
5 1
Remarque
Il y a une banque alimentaire avec $n = 6$ maisons à l'est. Le camion de Ket commence avec $x = 1$ unité de carburant et se déplace vers la maison 1. Il fait ensuite le plein à la maison 1 et se dirige vers la maison 2. À ce stade, il est optimal pour Ket d'utiliser sa baguette magique pour échanger les quantités de carburant dans les maisons 2 et 5, lui permettant de faire le plein de 3 unités de carburant et d'atteindre la maison 3. Par la suite, il peut faire le plein de 1 unité de carburant avant de voyager vers les deux maisons suivantes, en faisant le plein de 4 et 1 unités (en raison de l'échange précédent) de carburant dans les maisons 4 et 5 respectivement. Il lui restera alors 4 unités de carburant, ce qui le rend incapable de se rendre à la maison 6 car cela nécessite 6 unités de carburant. Comme Ket tombe en panne de carburant avant d'atteindre la maison 6, il ne peut se rendre qu'à la maison 5. De plus, il a dû effectuer un échange avec sa baguette magique. Par conséquent, $D = 5$ et $S = 1$.
Entrée 2
6 5 3 8 3 1 4 1 2 7 1 6 2 7
Sortie 2
6 1
Entrée 3
6 2 2 24 25 40 5 11 4 12 14 16 20 30
Sortie 3
3 2
Entrée 4
6 10 3 6 3 7 8 6 4 3 1 7 1 6
Sortie 4
5 1
Figure 1. Modélisation du royaume félin comme une route avec une banque alimentaire et n maisons.