Background

这天 R 喝醉了，正要开车回家。

Description

给定 n+1 个加油站编号为 0∼n，和一个容量为 m 的油箱。

每一个加油站都有一个 d i表示到编号为 i+1 加油站的距离，以及一个 pi，表示加 1 个单位油的价钱。

初始 R 的油箱没有油。现在要从编号为 0 0 的加油站出发，一直走到编号为 n 的加油站，问最小花费。若无法到达 n 号加油站输出 −1

Format Input

第 1 行两个整数，分别为 n 和 m 第2∼n+1 行，每行两个整数，分别表示 d0∼dn−1和p0∼pn−1

Output

一个整数，表示最小花费。或者一个整数 -1，表示无法到n

Samples

输入数据

3 15

10 2

9 1

8 3

输出数据

41

Limitation

1≤n≤5×10e5，

1≤m≤10e9，

1≤di,pi≤10e6