Usted se encuentra en el extremo de una calle de exactamente ~M~ metros de largo. A lo largo de la calle, hay ~N~ lugares donde puedes pedir un taxi. Los lugares donde se pueden pedir taxis están numerados de ~1~ a ~N~, siendo ~1~ el más cercano a ~t_i~ y ~N~ el más lejano a ~t_i~. La forma de cobrar los taxis es un poco inusual, ya que el solo hecho de pedir un taxi en el lugar ~i~, tiene un costo de ~c(i)~. Además del costo por pedir el taxi, el taxista cobrará una cantidad de d2 por hacer un viaje que recorra una distancia de ~d~ metros. Como estás lesionado no eres capaz de caminar ni siquiera un metro.

Tarea

Escriba un programa el cual:

• lea la cantidad de taxis, la longitud de la calle, el lugar donde se toman cada taxi y el costo inicial por pedir cada uno de ellos,

• determine el costo mínimo para viajar desde la posición inicial (la posición ~0~) a la posición final ~M~,

• escriba el costo mínimo encontrado.

Entrada

Línea 1: dos números ~N~ y ~M~.

Linea 2..~N+1~: cada una de estas líneas representa un lugar para tomar taxis y obtendrá dos números representando el lugar donde se toma el taxi (en metros) y el costo inicial por pedirlo.

Salida

Contiene un solo número el cual representa el costo mínimo para llegar a la posición ~M~.

Ejemplo de Entrada

2 50
0 2
25 1

Ejemplo de Salida

1253

Explicación de la salida

Cogemos el primer taxi en la posición ~0~, esto aumenta el costo en ~2~, viajamos ~25~ metros incrementando el costo en ~625~ para un total hasta aquí de ~627~. Se baja de este taxi y en ese lugar pide el segundo taxi y concluye el viaje con este, aumentando en ~1~ el costo por pedirlo más ~625~ por los ~25~ metros restantes para un costo total de ~1253~.

Consideraciones

• ~N \le 100 000~.

• Siempre podrás pedir un taxi en la posición número ~0~.

• El costo máximo siempre cabe en un entero de ~64 bits~.