宠物小精灵之收服（MOOC）程序设计算法基础第4题

某天早晨，在充满神奇生物的森林深处，出现了许多种类丰富的野生宠物小精灵。渴望驯服这些可爱的小精灵的小智也想拥有自己的宠物之一。然而，在驯服这些独特的野生小精灵时，并非易事——它们通常难以被驯服。每个独特的野生小精灵可能会让小智花费大量的时间与资源去征服它，在这个过程中还可能对皮卡丘造成一定的伤害并消耗其体力（从而导致其不得不停止活动）。当他的体力降至零或以下时——也就是无法继续战斗下去的时候——这些无法存活的小精灵也不会被驯服。”

我们假定当小智遇到野生小精灵时有两种行动选项：驯服该精灵或放弃与之互动。若选择驯服，则必须强制释放能够捕获该目标的小精灵球，并导致皮卡丘的能量损失；反之若放弃则不会影响资源。

小智的任务有两个：首要任务是尽可能多地驯服野生小精灵；若能在数量上与其它精灵相持不下，则希望皮卡丘所受伤害最少（剩余体力最多），毕竟它们仍需继续冒险。

目前掌握着关于小智及其宠物皮卡丘的信息：其中包含了关于各个小精灵的基本属性数据——包括在收服过程中会对主人格斗机造成伤害的数量以及完成收服所需消耗使用的精灵球数量。请问为了达到这一目的，请问应该如何选择这些值得培养的小精灵呢？

输入

第一行由三个整数组成参数N、M、K（其中N介于0到1000之间不包括端点值），分别依次表示小智拥有的精灵球个数、皮卡丘初始体力数值以及野生小精灵群体规模。接下来有K行详细说明每个野生小精灵的基