여행

바이트아사르(Byteasar)는 바이트랜드를 도는 자전거 여행을 계획하고 있다. 방문할 마을 $n+1$개와 이웃한 두 마을을 차례로 잇는 도로 $n$개를 골랐다. 각 도로에는 길이와 인상 계수(impression factor)라는 두 값이 있으며, 인상 계수는 양수일 수도 음수일 수도 있다.

이제 바이트아사르는 여행 전체를 여러 구간으로 나누어 하루에 한 구간씩 다니려고 한다. 각 구간은 고른 마을 중 하나에서 시작해 다른 마을에서 끝나야 하고, 한 구간의 총 길이는 $D$ 킬로미터를 넘을 수 없다. 한 구간의 인상 계수는 그 구간에 속한 도로들의 인상 계수 합을 제곱한 값이다. 즉, 어떤 구간이 인상 계수가 $w_1, w_2, \dots, w_m$인 도로들로 이루어져 있으면 그 구간의 인상 계수는 $(w_1 + w_2 + \dots + w_m)^2$이다.

바이트아사르는 여행 전체 구간들의 인상 계수 합을 최대한 작게 만들고 싶다. 그가 얻을 수 있는 가장 작은 합을 구하여라.

첫째 줄에 두 정수 $n$과 $D$가 주어진다 ($1 \le n \le 100\,000$, $1 \le D \le 10^9$). 각각 도로의 수와 한 구간의 최대 길이를 뜻한다.

다음 $n$개의 줄에는 각각 두 정수 $d_i$와 $w_i$가 주어진다 ($1 \le d_i \le D$, $-10\,000 \le w_i \le 10\,000$). 각각 $i$번째 도로의 길이와 인상 계수이다.

여행의 모든 구간의 인상 계수 합의 최솟값을 정수 하나로 출력한다.