#P6023. 走路

走路

题目背景

小 W 下载了一款运动软件。

题目描述

小 W 准备在接下来的 mm 天中锻炼,由于他不能走得太多以至于累死(怎么可能呢),所以他这 mm 天最多一共只能走 nn 步。
这个运动软件为了激励小 W 走路,推出了 kk 种激励措施,每种激励措施都形如“如果你第 pp 天走完了 qq 步,那么第 pp 天中接下来的每一步都会给你加 11 积分”。激励措施可以叠加,即走一步你可能可以获得多于 11 积分。
现在小 W 想知道,他最多可以获取多少积分呢?

输入格式

第一行三个整数 n,m,kn,m,k,意义如上。
接下来 kk 行,每行两个整数 p,qp,q,表示一个激励措施,意义如上。

输出格式

一行 11 个整数,表示 mm 天后最多可以获得的积分。

5 1 3
1 0
1 2
1 4

9

提示

样例解释:
只有一种方案,即在第一天走 55 步,第一、二步各获得 11 积分,第三、四步各获得 22 积分,第五步获得 33 积分,总计 99 积分。


数据范围:
对于 10%10\% 的数据,n,m,k10n,m,k\le10
对于 40%40\% 的数据,n,m,k103n,m,k \le 10^3
对于 100%100\% 的数据,1n10121\le n\le 10^{12}1m,k1051\le m,k\le 10^51pm1\le p\le m0qn0\le q\le n