26814번 - Szarlotka 다국어

Babcia Bitka, Bajtyna, robi najlepszą na świecie szarlotkę (przynajmniej według Bitka). Bitek poprosił ją o przepis i zebrał już wszystkie składniki, poza najważniejszym – jabłkami. Bitek ma w swoim sadzie N drzew ustawionych w jednej linii i ponumerowane kolejno od 1 do N. Na każdej jabłonce znajduje się dokładnie jedno jabłko, ale każde jest z innego gatunku. Na drzewie o numerze i znajduje się jabłko o poziomie słodkości równym Ai , przy czym niektóre jabłka mogą bardzo kwaśne i mogą mieć ujemny poziom słodkości. Do szarlotki babci Bajtyny potrzebne są jabłka, które sumarycznie będą dawać poziom słodkości równy K. Bitek zdecydował że wybierze sobie niepusty, spójny podciąg drzew (bez dziur) i zbierze z nich wszystkie jabłka, tak aby suma poziomów słodkości S tych jabłek była jak najbliższa K, tj. tak aby wyrażenie |S − K| było jak najmniejsze.

Napisz program, który wczyta poziomy słodkości kolejnych jabłek oraz poziom słodkości szarlotki babci Bajtyny, policzy jaka jest minimalna wartość |S − K| oraz wypisze wynik na standardowe wyjście.

W pierwszym wierszu wejścia znajdują się dwie liczby: N oraz K (1 ≤ N ≤ 500 000, −10¹⁸ ≤ K ≤ 10¹⁸). W drugim wierszu wejścia znajduje się ciąg N liczb całkowitych A_i oznaczające kolejno poziom słodkości jabłka na i-tym drzewie (−10¹² ≤ A_i ≤ 10¹²).

W pierwszym (i jedynym) wierszu wyjścia należy wypisać jedną liczbę całkowitą – minimalną możliwą do osiągnięcia wartość |S − K|.