暂无测试数据。

计蒜大道是一条长 $L$ 米的道路，道路上的坐标范围从 $0$ 到 $L$。路上有 $n$ 座房子，第 $i$ 座房子建在坐标为 $x_i$ 地方，其中住了 $r_i$ 人。

现在要在计蒜大道上建一条公路，政府希望让最多的人得到方便，因此希望所有的每一个的居民，从家到车站的距离的总和最短。那么问题来了，公交站应该建在哪里呢？请你求出这个最小的距离总和。

输入格式

第一行输入 $L\ (1\le L \le 10^{10})$、$n\ (1 \le n \le 10^5)$。

接下来 $n$ 行，每行两个整数 $x_i\ (0\le x_i \le L)$ 和 $r_i\ (1\le r_i \le 1000)$。每行的 $x_i$ 是从小到大递增的。

输出格式

一个整数，表示最小的每个人从家到车站的距离的总和。

100 3
20 3
50 2
70 1

110

100 2
0 1
100 10

100

10000000000 5
2222222222 700
3333333333 600
4444444444 500
5555555555 400
6666666666 300

3222222221900