OD C卷 - 贪心的歌手

贪心的歌手（200）

• 一个歌手从A城去B城参加演出，必须在T天内到达，不能往回走；
• 途经的每座城市都可以卖唱挣钱，在一座城市的第一天卖唱可以挣M，第二天挣M-D，后续每天都减少D，直到收入减少到0；
• 歌手到达一座城市后的第二天才可以卖唱，且卖唱后的第二天才可以出发；
• 贪心的歌手最多可以挣多少钱。
  输入描述：
  第一行输入T N， T为总天数（0,1000），N为路上经过的N座城市（0,100）
  第二行输入N+1个数字，表示每两座城市之间的耗时，总和<= T
  后续N行，每行输入 M D，表示每个城市的收入预期，M(0,1000) -> D(0, 100)
  输出描述：
  歌手最多可以赚的钱

示例1
输入：
10 2
1 1 2
120 20
90 10
输出：
540
说明：
总共10天时间，路上花费要4天，还有6天可以用来卖唱；
在第一座城市卖唱3天，赚钱120 + 100 + 80 = 300
在第二座城市卖唱3天，赚90 + 80 + 70 = 240
共计：300 + 240 = 540

 
params = [int(x) for x in input().split(" ")]
T = params[0]  
N = params[1]  
nums =  [int(x) for x in input().split(" ")]
matrix = []  
for i in range(N):
    matrix.append([int(x) for x in input().split(" ")])
 
 
for i in range(len(nums)):
    T-=nums[i]
 
moneys = []
i=0
while(True):
    if(i>=N):
        break
    else:
        temp1 = matrix[i][0]
        temp2 = matrix[i][1]
        j=0
        while(True):
            if(j>=T or temp1<=0):
                break
            else:
                moneys.append(temp1)
                temp1 = temp1- temp2
    i+=1
 
moneys = sorted(moneys, key=lambda x:-x)
 
result = 0
k = 0
while(True):
    if(k>=T):
        break
    else:
        result += moneys[k]
    k+=1
print(result)