解题思路

题目要在以下约束下最大化最终经验值：

• 初始经验 W、能量 E
• 每只怪 i：需要经验门槛 X[i]（不消耗经验，只是门槛），打完获得经验 Y[i]，消耗能量 Z[i]
• 最多打 K 只；若经验/能量不足以打任何怪则提前结束

关键观察：

题目内容

小明正在玩一款打怪升级游戏灰悟空，游戏中有 $N$ 个妖怪，每个妖怪包含三个正整数属性 ($X$ $Y$ $Z$)，$X$ 代表打怪需要的最小经验值（只是打怪需要的经验值门槛，打怪并不消耗经验），$Y$ 为打怪获得的经验收益，$Z$ 代表打怪消耗的能量。当前悟空的经验值为 $W$ ，能量为 $E$ ，当打死一个妖怪后，他将获得对应的经验值 $Y$ ，并消耗相应的能量 $Z$ 。由于时间有限，小明打算最多打 $K$ 个怪就结束游戏。你能帮他计算游戏结束时悟空的最大经验值和实际打怪个数吗？

备注：

1.当悟空经验或能量不足导致没有可打的妖怪时，游戏自动结束。

2.打死妖怪需要悟空的经验值大于等于打怪需要的最小经验值。

输入描述

• 第一行：$N$ $W$ $E$ $K$，其中

  • $N$ 代表妖怪总数，范围是 $[5,1000]$
  • $W$ 代表悟空的初始经验值，范围是 $[0,1000]$
  • $E$ 代表悟空的初始能量值，范围是 $[0,80000]$
  • $K$ 代表小明今天最大打怪个数,范围是 $[1,N-2]$

• 第$2$行：$X_1,X_2,...,X_n$，为各个妖怪需要的最小经验值列表，$x$的范围是[$0,500000$]

• 第$3$行：$Y_1,Y_2,...,Y_n$，为各个妖怪获得的经验收益值列表，$Y$的范围是[$1,1000$]

• 第$4$行：$Z_1,Z_2,...,Z_n$，为各个妖怪打怪消耗的能量值列表，$Z$的范围是[$1,100$]

输出描述

输出 $2$ 个数字，代表游戏结束时悟空的最大经验值和实际打怪个数

样例1

输入

5 0 100 3
0 5 5 8 9
5 3 4 10 6
10 20 30 40 50

输出

19 3

说明

共 $5$ 个妖怪,悟空初始经验为 $0$ ，能量值为 $100$，最多打 $3$ 个妖怪，先打唯一满足经验要求的妖怪 $1$ ，获取 $5$ 点经验，消耗 $10$ 点能量，此时悟空经验值为 $5$ ，能量值为 $90$，剩余打怪个数 $2$ ，再打经验收益较高的妖怪 $3$ ，获取 $4$ 点经验，消耗 $30$ 点能量，此时悟空经验值为 $9$ ，能量值为 $60$ ，剩余打怪个数 $1$ ，再打经验收益较高的妖怪 $4$ ，获取 $10$ 点经验，消耗 $40$ 点能量，打怪个数用完，游戏结束，此时悟空的经验值为 $19$ ，实际打怪 $3$ 个

样例2

输入

3 0 100 2
0 1 1
1 2 3
5 10 20

输出

4 2

说明

共 $3$ 个妖怪，悟空初始经验为 $0$ ，能量值为 $100$，最多打 $2$ 个妖怪，先打唯一满足经验要求的妖怪 $1$ ，获得 $1$ 点经验，消耗 $5$ 点能量，此时悟空经验值为 $1$ ，能量值为 $95$ ，剩余打怪个数 $1$ ，再打经验收益较高的妖怪 $3$ ，获取 $3$ 点经验，消耗 $20$ 点能量，打怪个数用完，游戏结束，此时悟空的经验值为 $4$ ，实际打怪 $2$ 个