题目描述

信是具有重量的。信封有重量，信纸也有重量。由于信封和信纸都很薄，我们认为每平方厘米信封的重量为 $x$ 毫克，每平方厘米信纸的重量为 $y$ 毫克。 此外，有的信封中还会有一些礼物，这些礼物一定有重量。

zyl 收到了 $n$ 封信，他能精确测量出每封信中信封的面积 $S$（单位：平方厘米）、信纸的面积 $s$（单位：平方厘米）以及整封信的重量 $M$（单位：毫克），保证这三个数据都是整数。在拆开信件的过程中，他会按照如下规则积累惊喜值（初始时惊喜值为 $0$）：

• 如果信封没有任何礼物（即信封中礼物重量为 $0$），他的惊喜值不变。但是，如果连续 $b$ 封及以上的信里都没有礼物，则从第 $b$ 封信开始，每拆开一封没有礼物的信，zyl 的惊喜值都会减半，然后向下取整，直到拆开一封有礼物的信。如果惊喜值原本即为 $0$，则不会变化。
• 如果信封里有礼物，设礼物的质量为 $M'$ 毫克，则 zyl 的惊喜值会增加 $M'$。如果礼物的质量大于信封和信纸的总质量，则会额外增加 $0.5\ M'$，然后向上取整。如果连续 $a$ 封及以上的信里有礼物，则从第 $a$ 封信开始，每拆开一封有礼物的信，zyl 的惊喜值都会在计算完这次本身的加成后再乘 $2$，直至拆开一封没有礼物的信。

现在按照 zyl 拆信的顺序给出 $n$ 封信的信息，请你求出 zyl 在拆信过程中最高的惊喜值和最终的惊喜值。

输入格式

输入共 $n+1$ 行。

第一行五个整数 $n,x,y,a,b$，含义如题所示。
接下来 $n$ 行，每行三个整数 $S,s,M$。表示这封信的信封面积，信纸面积和总质量，单位分别为平方厘米 、平方厘米、毫克。

输出格式

输出共一行两个整数，第一个表示拆信过程中的最高惊喜值，第二个表示最终的惊喜值，二者之间使用空格隔开。

6 1 1 2 2
5 3 10
6 2 12
2 3 5
2 3 11
3 5 8
2 2 4

21 10

提示

样例 1 解释

惊喜值的变化如下表： | 信的序号 | 礼物重量 | 惊喜值增加 | 额外增加 | 是否折半 | 是否翻倍 | 惊喜值 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | 1 | $2$ | $2$ | $0$ | 否 | 否 | $2$ | | 2 | $4$ | $4$ | $0$ | 否 | 是 | $12$ | | 3 | $0$ | $0$ | $0$ | 否 | 否 | $12$ | | 4 | $6$ | $6$ | $3$ | 否 | 否 | $21$ | | 5 | $0$ | $0$ | $0$ | 否 | 否 | $21$ | | 6 | $0$ | $0$ | $0$ | 是 | 否 | $10$ |

最高的惊喜值为 $21$，最终的惊喜值为 $10$。

数据规模与约定

对于 $40\%$ 的数据，$n\leq 1000$，任意时刻的惊喜值不会超过 $10^{9}$。
对于另外 $20\%$ 的数据，$a=b=n$。
对于 $100\%$ 的数据，$1\leq a,b\leq n\leq 10^{6}$，$1\leq x,y\leq 20$，$1\leq S,s\leq 500$，$x\times S+y\times s\leq M\leq 10^{5}$，任意时刻的惊喜值不会超过 $10^{18}$。