8480번 - Excursion 다국어

Byteasar is planning a bike trip around Byteland. He has selected n+1 towns that he is going to visit and n roads that connect the pairs of consecutive towns. Each road can be described using two parameters: its length and its impression-factor, which could be either positive or negative.

The last thing that Byteasar has to do is to divide the trip into segments that will correspond to consecutive days of the excursion. Each segment must start and end in one of the selected towns and its length may not exceed D kilometers. The impression-factor of a segment is defined as a square of the sum of impression-factors of the roads forming the segment. More formally, if a segment consists of roads with impression-factors w₁, w₂, ..., w_m, then the impression-factor of the whole segment equals (w₁ + w₂ + ... + w_m)².

A bit surprisingly, Byteasar would like to minimize the sum of impression-factors of all the segments in his trip. Even though this idea sounds ridiculous, please help him find out how small sum can he get.

The first line of input contains two integers n and D (1 ≤ n ≤ 100 000, 1 ≤ D ≤ 10⁹) that represent the number of roads in Byteasar's trip and the upper bound for the length of a single segment of the trip. The following n lines contain descriptions of the roads: the i-th line contains two integers d_i and w_i (1 ≤ d_i ≤ D, -10 000 ≤ w_i ≤ 10 000) that denote the length and the impression-factor of the i-th road.

The only line of output should contain one integer: the minimum possible sum of impression-factors of all the segments in Byteasar's trip.