该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

沐沐和 hw 是一对相隔千里的异地恋情侣，沐沐的 24 岁生日快到了，hw 想给她一份独一无二的惊喜 —— 收集 100 座城市的 “思念碎片”。每一片碎片都来自他们共同朋友的祝福，承载着两人异地相守的点滴回忆：有他们第一次视频时背景里的梧桐叶，有沐沐生病时 hw 连夜寄去的感冒药包装，还有每次见面时高铁站的打卡照片。
规则是这样的：hw 需要在沐沐生日前 T 天内收集完 m 片碎片，每天他能攒下 k 个 “心意信物”（信物可累积，代表他每天挤出来的时间和精力）。每片碎片有三个要求：发布时间 t_i（只有到了这天及之后才能尝试收集）、所需心意信物 c_i（收集时必须一次性拿出足够数量）、冷却时间 d_i（收集完这片碎片后，接下来 d_i 天里无法收集任何碎片 —— 因为他要花时间整理这份思念，录制成视频发给沐沐）。
收集还有几个约定：① 每天只能尝试收集一次，优先收集还没收集、且已到发布时间的碎片中编号最小的那片（按朋友发送的顺序）；② 若当天处于冷却期，无法收集，只能攒信物；③ 到了截止日 T 天，无论是否收集完，都要停止。hw 想知道，自己最终能不能在生日前集齐所有碎片？如果能，总共用了多少天，还剩多少信物？如果不能，收集到了几片，还剩多少信物？

Description

给定四个参数：截止天数 T、每天获得的心意信物数 k、碎片总数 m，以及 m 片碎片的信息（每片含发布时间 t_i、所需信物 c_i、冷却时间 d_i，碎片编号 1~m 按输入顺序排列）。请模拟 hw 收集碎片的过程，输出最终结果：
若在 T 天内收集完所有 m 片碎片：输出两个整数，分别为 “总耗时（从第 1 天到收集完最后一片的天数）” 和 “剩余信物数”；
若未收集完：输出两个整数，分别为 “收集到的碎片数量” 和 “剩余信物数”。

Format

Input

第一行三个整数 T、k、m（满足 1≤T≤1000，1≤k≤100，1≤m≤50）；
接下来 m 行，每行三个整数 t_i、c_i、d_i（满足 1≤t_i≤T，1≤c_i≤1000，0≤d_i≤10），分别对应第 i 片碎片的发布时间、所需信物数、冷却时间

Output

两个整数，按题目要求输出。

Samples

20 3 3
1 5 2
3 4 1
5 6 0

7 0

Limitation

1s, 1024KiB for each test case.