h2. Restricţii

* $1 ≤ N ≤ 100 000$
* $1 ≤ C ≤ 20 000 000$

* $1 ≤ N ≤ 100000$
* $1 ≤ C ≤ 20000000$

* $1 ≤ s{~i~} ≤ 20 000 000$, pentru orice i, $1 ≤ i ≤ N$.
* $-10000 ≤ s{~i~} ≤ 10000$, pentru orice i, $1 ≤ i ≤ N$.

* Pentru $20%$ din teste, fiecare cameră are maximum $2$ vecini.
* Pentru $30%$ din teste, $N ≤ 1 000$.
* Se garantează că pentru orice cameră $x$, numărul total de spiriduşi aflaţi în camerele de pe drumul cel mai scurt de la camera $1$ la camera $x$ nu depăşeşte $1 000 000 000$.

h2. Exemplu