Po pomyślnym zapobieżeniu wyginięciu kotów podczas corocznych obchodów Narodowego Dnia Kota (NCD), kot Ket otrzymał skargi na głód z królestwa kanibalistycznych kotów. W związku z tym Ket otrzymał zadanie dostarczenia żywności, aby zapobiec ponownemu uciekaniu się przez nie do kanibalizmu.
To kocie królestwo można modelować jako bardzo długą drogę biegnącą z zachodu na wschód. Na zachodnim krańcu drogi znajduje się bank żywności. Na wschód od banku żywności znajduje się $n$ kocich domów, ponumerowanych od 1 do $n$. Gwarantuje się, że $n$ jest liczbą parzystą. Pierwszy dom znajduje się $d[1]$ kilometrów na wschód od banku żywności. Dla $i \ge 2$, $i$-ty dom znajduje się $d[i]$ kilometrów na wschód od $(i-1)$-go domu.
Ket będzie prowadził ciężarówkę dostawczą, aby dostarczyć żywność do domów. Ciężarówka startuje z banku żywności i początkowo posiada $x$ jednostek paliwa. 1 jednostka paliwa pozwala Ketowi przejechać ciężarówką 1 kilometr wzdłuż drogi.
$i$-ty dom posiada $f[i]$ jednostek paliwa do wykorzystania przez ciężarówkę. Ciężarówka ma nieskończoną pojemność zbiornika paliwa i zatrzymuje się tylko wtedy, gdy zabraknie jej paliwa. Po wyjeździe z banku żywności ciężarówka nie musi do niego wracać.
Rysunek 1. Model drogi z bankiem żywności i kocimi domami.
Dodatkowo, Ket posiada magiczną różdżkę. Jednym machnięciem różdżki może zamienić ilość paliwa przechowywaną w $i$-tym oraz $(n - i + 1)$-szym kocim domu. Ta zamiana może nastąpić tylko wtedy, gdy paliwo w obu domach nie zostało jeszcze zużyte. Pomóż Ketowi znaleźć indeks najdalszego domu $D$, do którego może dotrzeć, używając dowolnej liczby zamian. Pomóż również Ketowi znaleźć minimalną liczbę zamian $S$ potrzebną do dotarcia do domu $D$.
Wejście
Twój program musi czytać dane ze standardowego wejścia.
Pierwsza linia wejścia zawiera dwie liczby całkowite $n$ oraz $x$ oddzielone spacją.
Druga linia wejścia zawiera $n$ liczb całkowitych $d[1], d[2], \dots, d[n]$ oddzielonych spacjami.
Trzecia linia wejścia zawiera $n$ liczb całkowitych $f[1], f[2], \dots, f[n]$ oddzielonych spacjami.
Wyjście
Twój program musi wypisać dane na standardowe wyjście.
Wypisz dwie liczby całkowite oddzielone spacją w jednej linii. Pierwsza liczba powinna być $D$, indeksem najdalszego domu, do którego Ket może dotrzeć, a druga $S$, minimalną liczbą zamian potrzebną do dotarcia do domu $D$.
Ograniczenia
Dla wszystkich przypadków testowych dane wejściowe spełniają następujące warunki:
- $2 \le n \le 500\,000$
- $n$ jest liczbą parzystą.
- $1 \le d[i] \le 10^9$ dla wszystkich $1 \le i \le n$
- $1 \le f[i] \le 10^9$ dla wszystkich $1 \le i \le n$
- $d[1] \le x \le 10^9$
Twój program będzie testowany na instancjach wejściowych spełniających następujące ograniczenia:
| Podzadanie | Punkty | Dodatkowe ograniczenia | ||
|---|---|---|---|---|
| 0 | 0 | Przykłady testowe | ||
| 1 | 7 | $ | f[i] - f[n - i + 1] | = k$ dla pewnej stałej $k$, dla wszystkich $1 \le i \le n$ |
| 2 | 12 | $n \le 40$ | ||
| 3 | 14 | $f$ jest niemalejący ($f[i] \le f[i + 1]$ dla wszystkich $1 \le i \le n - 1$) | ||
| 4 | 19 | $D \le \frac{n}{2}$ | ||
| 5 | 21 | $n \le 5000$ | ||
| 6 | 27 | Brak dodatkowych ograniczeń |
Uwaga: Wartość bezwzględna liczby $x$, oznaczana jako $|x|$, jest nieujemną liczbą równą odległości między 0 a $x$ na osi liczbowej. Na przykład $|5| = 5$ oraz $|-5| = 5$.
Przykład
Wejście 1
6 1 1 1 3 1 1 6 1 1 1 4 3 2
Wyjście 1
5 1
Uwagi
Ten przypadek testowy jest poprawny dla podzadań 2, 5 i 6. Istnieje bank żywności z $n = 6$ domami na wschód od niego. Ciężarówka Keta startuje z $x = 1$ jednostką paliwa i jedzie do domu 1. Następnie tankuje w domu 1 i jedzie do domu 2. W tym momencie optymalne dla Keta jest użycie magicznej różdżki, aby zamienić ilości paliwa w domach 2 i 5, co pozwala mu zatankować 3 jednostki paliwa i dotrzeć do domu 3. Następnie może zatankować 1 jednostkę paliwa przed podróżą do kolejnych dwóch domów, tankując odpowiednio 4 i 1 jednostkę (z powodu wcześniejszej zamiany) paliwa w domach 4 i 5. Będzie miał wtedy 4 jednostki paliwa, co uniemożliwi mu dotarcie do domu 6, ponieważ wymaga on 6 jednostek paliwa. Ponieważ Ketowi kończy się paliwo przed dotarciem do domu 6, może dotrzeć tylko do domu 5. Ponadto musiał wykonać jedną zamianę swoją magiczną różdżką. Zatem $D = 5$ oraz $S = 1$.
Wejście 2
6 5 3 8 3 1 4 1 2 7 1 6 2 7
Wyjście 2
6 1
Uwagi
Ten przypadek testowy jest poprawny dla podzadań 1, 2, 5 i 6.
Wejście 3
6 2 2 24 25 40 5 11 4 12 14 16 20 30
Wyjście 3
3 2
Uwagi
Ten przypadek testowy jest poprawny dla podzadań 2, 3, 4, 5 i 6.
Wejście 4
6 10 3 6 3 7 8 6 4 3 1 7 1 6
Wyjście 4
5 1
Uwagi
Ten przypadek testowy jest poprawny dla podzadań 2, 5 i 6.