饮水机

题目背景

集训队的走廊里只有一台饮水机。这台机器年纪比队长还大，水箱容量有限，接水的人一多水箱就会见底，见底之后还得先清洗滤芯才能继续用。队员们排成长队，谁也不想多等一秒。

题目描述

饮水机的水箱容量为 $C$ 毫升，一开始水箱是满的。机器出水与注水的速度都是 $1$ 毫升每秒：接走 $x$ 毫升水需要 $x$ 秒，把空水箱重新加满需要 $C$ 秒。

这台机器还有一个毛病：水箱一旦见底，就必须先花 $R$ 秒清洗滤芯，清洗结束后水箱重新变满，才能继续出水。

有 $n$ 名队员按给定顺序依次来接水，第 $i$ 名队员需要 $d_i$ 毫升水。机器按顺序为每个人服务，对第 $i$ 个人：

• 如果水箱里剩余的水不少于 $d_i$ 毫升，那么立刻接水，耗时 $d_i$ 秒，水箱剩余水量减少 $d_i$ 毫升；
• 如果水箱里剩余的水少于 $d_i$ 毫升，而 $d_i \le C$，那么机器先花 $R$ 秒清洗水箱并把它加满，再为他接水 $d_i$ 秒，这一过程共耗时 $R + d_i$ 秒，结束时水箱剩余 $C - d_i$ 毫升；
• 如果 $d_i > C$，那么无论等多久他都接不满自己的水杯，这种情况被认定为机器无法完成任务。

请你判断任务能否完成：若可以，输出接完 $n$ 个人水杯所需的总秒数；否则输出 -1。

输入格式

从标准输入读入数据。

第一行三个整数 $n, C, R$。

第二行 $n$ 个整数 $d_1, d_2, \dots, d_n$，含义如题面所述。

输出格式

输出到标准输出。

输出一行一个整数，表示总耗时；若任务无法完成，输出 -1。

样例 1 输入

3 5 2
3 4 3

样例 1 输出

14

样例 1 解释

第 1 名队员需要 $3$ 毫升，水箱中有 $5$ 毫升，直接接水耗时 $3$ 秒，水箱剩 $2$ 毫升。

第 2 名队员需要 $4$ 毫升，而水箱里只剩 $2$ 毫升，于是先清洗 $2$ 秒再加满，然后接水 $4$ 秒，共 $6$ 秒，水箱剩 $1$ 毫升。

第 3 名队员需要 $3$ 毫升，而水箱里只剩 $1$ 毫升，同样先清洗 $2$ 秒再加满，然后接水 $3$ 秒，共 $5$ 秒，水箱剩 $2$ 毫升。

总耗时为 $3 + 6 + 5 = 14$ 秒。

样例 2 输入

2 3 1
4 1

样例 2 输出

-1

数据范围

特殊性质 A：$R = 0$。

特殊性质 B：所有 $d_i$ 都不超过 $C$，也就是说任务一定可以完成。

对于所有测试数据，$1 \le n \le 10^5$，$1 \le C, R \le 10^9$，$1 \le d_i \le 10^9$。总耗时可能超过 $2^{31} - 1$。

提交说明

本题使用标准输入输出。程序应从标准输入读入数据，并将答案输出到标准输出。