← 返回题目列表

AtCoder · abc432_c

E. 糖果劫

中文机器翻译题面 查看原题

分数: 350 点

问题陈述

你有两种类型的糖果无限供应:小糖果和大糖果。 一颗小糖果的重量是 X 克,一块大糖果的重量是 Y 克。大糖果比小糖果重(也就是说, X < Y).

有 N 儿童,已编号 1 to N.

您决定分发糖果,以满足以下条件:

  • 对于 i=1,\dots,N,孩子 i 准确接收 A_i 糖果共有两种类型。
  • 分配给的糖果总重量 N 孩子们都是平等的。

判断是否存在满足条件的分发方式。如果存在,请找出分发的大糖果数量的最大可能值。

约束

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq X < Y \leq 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N X Y
A_1 \dots A_N

输出

如果没有满足条件的分配方法,则输出 -1.

如果存在满足条件的分配方法,则输出该分配方法中分配的大糖果数量的最大可能值。


示例输入 1

3 6 8
11 10 13

示例输出 1

18

您可以按如下方式分发糖果,以便分发给孩子们的糖果总重量都相等。

  • 儿童 1 收到 4 小糖果和 7 大糖果。总重量为 6 \times 4 + 8 \times 7 = 80 克。
  • 儿童 2 收到 0 小糖果和 10 大糖果。总重量为 6 \times 0 + 8 \times 10 = 80 克。
  • 儿童 3 收到 12 小糖果和 1 大糖果。总重量为 6 \times 12 + 8 \times 1 = 80 克。

在这种分配方式中,总共 18 大糖果已分发。

不存在满足条件且分配多于的分配方法 18 大糖果。因此,答案是 18.


示例输入 2

2 3 4
3 5

示例输出 2

-1

没有满足条件的分配方法。


示例输入 3

8 4 32
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

示例输出 3

8000000000

答案可能不适合 32 位整数。