【问题背景】

在xm的XX宾馆里，可以免费拨打国内长途，因此，sxc同学就开始狂打电话，至于打给谁，这里不好透露。还好sxc忙着打电话，我们3个就不用抢着2台电脑上网了——电脑就由wl和zsx占领了，嘿嘿。但如果电话不是免费的，只是价格低廉，sxc同学就该考虑一下怎么打最划算。虽然sxc同学是编程强人，但此时心急如焚的他，已经不能安心下来编程了；wl和zsx虽然也是编程强人，但此时忙着上网打游戏的他们，也不愿意编程，毕竟还是打游戏爽些。因此sxc只有求助于你了，希望你能编程求出在一定条件下使打电话的时间最长的方案。

【问题描述】

假设sxc拥有的钱为 n wsz（wsz是wl，sxc，zsx自创的计算钱的单位，至于怎么换算成RMB或USD，没有人清楚）。给出每一通电话从第X分钟打到第Y分钟需要花费的钱C（若X<Z<Y,则从第X分钟打到第Z分钟也要花费C）。由于老师会来查房，因此sxc必须在对应的时刻挂断电话或者不打电话。你可以认为老师查房不需要花费时间，即若老师会在第B 分钟末来查房，sxc可以在B分钟末时先挂断电话，再在B+1分钟始拿起电话，中途不消耗任何时间——毕竟心情急迫啊。需要注意的是，老师最后一次查房后不能再打电话。sxc希望你求出能打电话的最长时间，并为他省下尽可能多的钱。

【输入格式】phone.in

第1行是一个整数n（1<=n<=10^9），一个整数k（1<=k<=10）和一个整数t（1<=t<=500），分别表示sxc拥有的钱，老师查房的次数和每次通话的最长通话时间；

第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，X(i+1)=Yi +1，Xi<=Yi，Ym=t。

【输出格式】phone.out

你的程序需要输出两行： 第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 wsz ，剩余4 wsz，为一种最佳方案。

方案二：

第1次从第1 分钟打到第3 分钟后挂断，共3分钟，老师第4分钟末来查房；

第2次从第5分钟打到第7 分钟后挂断，共3分钟，老师第7分钟末来查房；

第3次从第8分钟打到第13分钟后挂断，共6分钟，老师第13分钟末（最后一次）来查房，此后不能再打电话；

总共打了12分钟，用掉9996 wsz ，剩余4 wsz，为另一种最佳方案。

【数据范围】

对于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。