虹猫成功救出蓝兔后，为了帮助蓝兔摆脱心理阴影，和蓝兔一起玩起了开心农场的游戏。这个游戏开始时有一个体验期，系统会分配给玩家一定数量的金币。规定在同一时期只能种植一种作物，但是只要金币允许，玩家可以在土地上种植任意多的同一种作物。种子需要一定费用，作物一旦成熟玩家就收获并售出作物。系统将根据玩家在体验期结束时所拥有的金币数量给予相应奖励（如果作物在体验期结束的时刻尚未成熟，则不计入在内）。农场中的作物有的在体验期内全时段开放种植，而有的则只能在某个时段种植。每种作物播种以后需要经过一定的时间才会成熟，而播种、收获的时间可以忽略不计。虹猫是个爱思考的孩子，他想在体验期内获得最多的金币，应该怎么做呢？

共K+1行，第一行有3个正整数M、D和K，分别用一个空格隔开，其中M表示游戏开始时所拥有的金币数量（1≤M≤200），D表示体验期的时长（1≤D≤10000，单位：小时），K表示作物的种类数（1≤K≤5000）。接下来K行，每行有5个用空格隔开的非负整数，分别是S、F、T、B、E，其中S表示该作物的种子单价（1≤S≤100），F表示该作物的售出价格（S≤F≤1000），T表示该作物成熟需要的时间（1≤T≤100，单位：小时），B和E分别表示该作物可以种植的开始时间和结束时间（即若当前时刻为t，且Bi≤t＜Ei，则此时第i种作物可以播种，且其成熟时间可在Ei时刻以后，1≤i≤K；B、E单位为时，0≤B≤D，B＜E≤10000）。

一个正整数，表示体验期结束时虹猫能够拥有的最多金币数。

限制：
40%的数据，D≤100，K≤10
100%的数据，D≤10000，K≤5000

 AHOI初中 2011 level5