Perfil do reservatório

Time limit: 4000 msMemory limit: 256 MB

Um reservatório é dividido em $n$ compartimentos de mesma largura, dispostos em uma linha. O compartimento $i$ deve receber uma quantidade inteira $x_i$ de água, com $l_i\le x_i\le r_i$ . O total de água deve ser exatamente $S$ .

A irregularidade de um perfil é a maior diferença absoluta entre quantidades em compartimentos vizinhos: $\max_{1\le i<n}|x_i-x_{i+1}|.$ Para , a irregularidade é definida como zero.

Determine a menor irregularidade possível, ou informe que não existe perfil com o total exigido.

Input

A primeira linha contém $n$ e $S$ ( $1\le n\le 200000$ , $0\le S\le 10^9n$ ). Cada uma das próximas linhas contém e ().

Output

Imprima a menor irregularidade ou -1 se nenhum perfil válido existir.

Samples

Sample 1

Input

Output

O perfil $(1,1,2)$ tem total 4 e irregularidade 1. Um perfil de irregularidade zero teria três quantidades iguais e, portanto, total múltiplo de 3.

Sample 2

Input

Output

O total força o perfil $(0,4,4)$ , cuja irregularidade é 4.

Sample 3

Input

2 1
1 2
1 2

Output

-1

Os limites inferiores já exigem duas unidades, mas o total pedido é 1.