#QY0028. 原神痣·战略版

原神痣·战略版

题目背景

Dw正在玩《原神》这款开放世界RPG游戏的时候,突然看到了一个同人游戏,名字叫《原神痣·战略版》。这个游戏十分好玩,可是没过多久就关服了,于是他决定自己做一个

题目描述

这个游戏里面,你有 nn 个卡牌,每个卡牌有对应的伤害,但同时卡牌只能按从左往右的顺序依次打出,不过可以丢弃当前牌。同时,地方有一个血量为 hh ,防御为 ss 的boss,并且这个boss可以秒杀掉你当前出的一张牌。现在,请你设计一个程序,此程序会输出能造成的最高伤害(总和),boss的剩余血量

输入

第一行三个正整数 n,h,sn, h, s ,分别表示卡牌个数,boss血量以及防御值

接下来 nn 个整数,每个正整数表示当前第 ii 个卡牌的攻击力(可能为负数)

输出

一行两个整数,分别表示造成的最高伤害总和,以及boss的剩余血量

样例

6 114 5
11 -4 51 -4 19 -1
42 72

样例解释

可以所有牌都选择,减去防御后最高伤害为42(11+ -4 + 51 + -4 + 19 + -1 - 5 - 5 - 5 - 5 - 5 - 5),剩余血量为72

数据范围

对于 100100% 的数据,保证 1n,h,s1051 \leq n, h, s \leq 10^5ai105ai \leq 10^5