FRAKTAL - konkurs programistyczny

Codziennie do biurowca przychodzi n osób. Osoba, która przychodzi do budynku jako i-ta ustawia się na końcu kolejki do wind w jednostce czasu t_i i chce się dostać na piętro p_i. Osoby w kolejce nie zamieniają się miejscami, ani nie opuszczają kolejki.

Każda winda może zabrać 1 osobę. Przejechanie 1 piętra w górę albo w dół zajmuje 1 jednostkę czasu. Czas wsiadania do windy i wysiadania z windy zajmuje 0 jednostek czasu. Po dowiezieniu osoby na wybrane piętro, winda wraca na piętro 0. W 0 jednostce czasu wszystkie windy znajdują się na piętrze 0.

Odpowiedz na pytanie, ile minimalnie wind znajduje się w biurowcu jeżeli wiadomo, że żadna z n osób nie czekała żeby wsiąść do windy dłużej niż m jednostek czasu?

Wejście

W pierwszej linii wejścia znajdują się dwie liczby całkowite n (7 ≤ n ≤ 100000) oraz m (0 ≤ m ≤ 199998000000000) opisane w treści powyżej.

W drugiej linii wejścia znajduje się n liczb całkowitych oddzielonych pojedynczą spacją. Liczba i-ta w kolejności określa jednostkę czasu t_i (1 ≤ t_i ≤ 1000000000; t_i ≤ t_i+1), w której i-ta osoba ustawiła się na końcu kolejki do wind.

W trzeciej linii wejścia znajduje się n liczb całkowitych oddzielonych pojedynczą spacją. Liczba i-ta w kolejności określa piętro p_i (1 ≤ p_i ≤ 1000000000), na które chce się dostać i-ta osoba.

Wyjście

Na wyjściu należy wypisać odpowiedź na pytanie, ile minimalnie wind znajduje się w biurowcu jeżeli wiadomo, że żadna z n osób nie czekała żeby wsiąść do windy dłużej niż m jednostek czasu?

Przykład

Wejście:

7 12
3 3 3 3 14 15 15
2 5 3 10 7 6 20

Wyjście:

3

Wyjaśnienie do przykładu:

Przebieg testu przykładowego w formacie: jednostka czasu - zdarzenie

• j.cz. 0 - Windy 1, 2 i 3 znajdują się na 0 piętrze.
• j.cz. 3 - Osoba 1 ustawia się na końcu kolejki do wind.
• j.cz. 3 - Osoba 2 ustawia się na końcu kolejki do wind.
• j.cz. 3 - Osoba 3 ustawia się na końcu kolejki do wind.
• j.cz. 3 - Osoba 4 ustawia się na końcu kolejki do wind.
• j.cz. 3 - Osoba 1 wsiada do windy numer 1 i odjeżdża na 2 piętro. Czas oczekiwania: 0
• j.cz. 3 - Osoba 2 wsiada do windy numer 2 i odjeżdża na 5 piętro. Czas oczekiwania: 0
• j.cz. 3 - Osoba 3 wsiada do windy numer 3 i odjeżdża na 3 piętro. Czas oczekiwania: 0
• j.cz. 7 - Winda 1 wraca na 0 piętro.
• j.cz. 7 - Osoba 4 wsiada do windy numer 1 i odjeżdża na 10 piętro. Czas oczekiwania: 4
• j.cz. 9 - Winda 3 wraca na 0 piętro.
• j.cz. 13 - Winda 2 wraca na 0 piętro.
• j.cz. 14 - Osoba 5 ustawia się na końcu kolejki do wind.
• j.cz. 14 - Osoba 5 wsiada do windy numer 2 i odjeżdża na 7 piętro. Czas oczekiwania: 0
• j.cz. 15 - Osoba 6 ustawia się na końcu kolejki do wind.
• j.cz. 15 - Osoba 7 ustawia się na końcu kolejki do wind.
• j.cz. 15 - Osoba 6 wsiada do windy numer 3 i odjeżdża na 6 piętro. Czas oczekiwania: 0
• j.cz. 27 - Winda 1 wraca na 0 piętro.
• j.cz. 27 - Winda 3 wraca na 0 piętro.
• j.cz. 27 - Osoba 7 wsiada do windy numer 1 i odjeżdża na 20 piętro. Czas oczekiwania: 12
• j.cz. 28 - Winda 2 wraca na 0 piętro.
• j.cz. 67 - Winda 1 wraca na 0 piętro.