#P6023. 走路
走路
题目背景
小 W 下载了一款运动软件。
题目描述
小 W 准备在接下来的 天中锻炼,由于他不能走得太多以至于累死(怎么可能呢),所以他这 天最多一共只能走 步。
这个运动软件为了激励小 W 走路,推出了 种激励措施,每种激励措施都形如“如果你第 天走完了 步,那么第 天中接下来的每一步都会给你加 积分”。激励措施可以叠加,即走一步你可能可以获得多于 积分。
现在小 W 想知道,他最多可以获取多少积分呢?
输入格式
第一行三个整数 ,意义如上。
接下来 行,每行两个整数 ,表示一个激励措施,意义如上。
输出格式
一行 个整数,表示 天后最多可以获得的积分。
5 1 3
1 0
1 2
1 4
9
提示
样例解释:
只有一种方案,即在第一天走 步,第一、二步各获得 积分,第三、四步各获得 积分,第五步获得 积分,总计 积分。
数据范围:
对于 的数据,。
对于 的数据,。
对于 的数据,,,,。