2140: 贪心的歌手
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：1
Solved：1
Description
一个歌手准备从A城去B城参加演出
1.按照合同，他必须在T天内赶到
2.歌手不能往回走
3.每两座城市之间需要的天数都可以提前获知
4.歌手在每座城市都可以在路边卖唱赚钱。经过调研，歌手提前获知了每座城市卖唱的收入预期: 如果在一座城市第天卖唱可以赚M，后续每天的收入会减少D(第二天赚的钱是M-D，第三天是M-2D...如果收入减到0就不会再少了.
5.歌手到达后的第二天才能开始卖唱。如果今天卖过唱，第二天才能出发
贪心的歌手最多可以赚多少钱?
Input
第一行两个数字 T和 N，中间用空格隔开
T代表总天数:
N代表路上经过N座城市:
0
Output
一个数字。代表歌手最多可以赚多少钱。
Sample Input Copy
10 2
1 1 2
120 20
90 10Sample Output Copy
540