1831: 打电话
题目描述
在市区经过一次M的N次方的搜索，小X终于来到了镇江中学。经过带队老师的注册、登记。小X终于来到了本次冬令营的住宿地――镇江中学学生宿舍。安顿好自己的行李后，小X赶紧忙着给自己的亲戚、朋友、同学、父母报个平安。由于电话不是免费的，所以小X同学就该考虑一下怎么打最划算。虽然小X同学是编程强人，但此时心急如焚的他，已经不能安心下来编程了。因此小X只有求助于你了，希望你能编程求出在一定条件下使打电话的时间最长的方案。
假设小X拥有的钱为 n 元。给出每一通电话从第X分钟打到第Y分钟需要花费的钱C（若X<Z<Y,则从第X分钟打到第Z分钟也要花费C）。由于其他同学也要来打电话，因此小X必须在对应的时刻挂断电话或者不打电话。你可以认为其他人打电话的时间很短以至于不需要花费时间，即若其他同学在第B 分钟末来打电话，小X可以在B分钟末时先挂断电话，再在B+1分钟始拿起电话，中途不消耗任何时间――毕竟心情急迫啊。需要注意的是，其他同学最后一次打完电话后小X就不能再打电话。小X希望你求出能打电话的最长时间，并为他省下尽可能多的钱。
输入
第1行是一个整数n（1<=n<=10^9），一个整数k（1<=k<=10）和一个整数t（1<=t<=500），分别表示小X拥有的钱，其他同学打电话的次数和小X每次通话的最长通话时间；
第2行有k个用空格格开的整数Bi ，分别表示其他同学会在对应的时刻来打电话。且相邻两次间隔时间不超过t；
第3行是一个整数m（1<=m<=20），表示接下来有m行；
从第4行到第3+m行中
第2+i行有Xi，Yi，Ci共3个整数，表示从第Xi分钟打到第Yi分钟的费用是Ci（Ci<=10^8），因此有X1=1，Xi+1=Yi +1，Xi<=Yi，Ym=t。
输出
你的程序需要输出两行：
第1行一个整数，是最多可以打电话的分钟数；
第2行一个整数，是在打电话的分钟数最多时，能剩下的最多的钱数。
样例输入 复制
10000 3 9
4 7 13
3
1 3 2499
4 6 2499
7 9 3000
样例输出 复制
12
4
提示
样例说明
方案一：
第1次从第1 分钟打到第3 分钟后挂断，共3分钟，其他同学第4分钟末来打电话；
第2次从第5分钟打到第7 分钟后挂断，共3分钟，其他同学第7分钟末来打电话；
第3次从第8分钟打到第10分钟后挂断，共3分钟；
第4次从第11分钟打到第13 分钟后挂断，共3分钟，其他同学第13分钟末（最后一次）来打电话，此后不能再打电话；
总共打了12分钟，用掉9996元 ，剩余4 元，为一种最佳方案。
方案二：
第1次从第1 分钟打到第3 分钟后挂断，共3分钟，其他同学第4分钟末来打电话；
第2次从第5分钟打到第7 分钟后挂断，共3分钟，其他同学第7分钟末来打电话；
第3次从第8分钟打到第13分钟后挂断，共6分钟，其他同学第13分钟末（最后一次）来打电话，此后不能再打电话；
总共打了12分钟，用掉9996 元 ，剩余4 元，为另一种最佳方案。
数据范围
对于20%的数据，k=1，m<=5，t<=5；
对于40%的数据，k=1，n<=10000；
对于60%的数据，k<=3；
对于100%的数据，k<=10，n<=10^9，m<=20，t<=500。