← 返回题目列表

Codeforces · 200/E

E. 拖拉机学院

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

虽然大多数学生仍在参加考试,但拖拉机学院已经完成了夏季考试。事实上,学生在这所学院只学习一门科目——操作拖拉机的艺术。因此,在学期结束时,学生只能得到一分:三分(满意)、四分(良好)或五分(优秀)。不幸的是,那些得分较低的人会被开除。

学院有n名学生,奇怪的是,他们每个人都可以获得奖学金。每个学期的奖学金数额各不相同。由于期末考试刚刚结束,是时候确定下学期末的奖学金数额了。

拖拉机学院的奖学金每月预算为s卢布。为了最佳地分配预算,您必须遵循以下规则:

- 考试成绩相同的学生,应获得相同的奖学金;
- 让我们将考试成绩为 3、4 和 5 分的学生的奖学金金额(以卢布为单位)分别表示为 k3、k4 和 k5。 k3、k4和k5的值必须是整数并且满足不等式0 ≤ k3 ≤ k4 ≤ k5;
- 假设 c3、c4、c5 分别显示有多少学生在考试中获得了 3、4 和 5 分。奖学金预算应全部花在他们身上,即c3·k3 + c4·k4 + c5·k5 = s;
- 让我们介绍一下函数 $$f(k_{3},k_{4},k_{5})=|c_{3}\cdot k_{3}-c_{4}\cdot k_{4}|+|c_{4}\cdot k_{4}-c_{5}\cdot k_{5}|$$ — 该值显示奖学金在学生之间的分配情况。在最优分布函数中,f(k3, k4, k5) 取最小可能值。

给定考试成绩和预算规模 s,您必须找到奖学金的最佳分配。

输入

第一行有两个整数 n, s (3 ≤ n ≤ 300, 1 ≤ s ≤ 3·105) — 分别是学生人数和奖学金预算规模。第二行包含n个整数,其中第i个数字代表第i个学生的考试成绩。保证每个分数至少分配给一名学生。

输出

在一行上打印三个整数 k3、k4 和 k5 — 代表奖学金最佳分配的寻求值。如果有多个最佳答案,请打印其中任何一个。如果没有答案,则打印-1。

示例

输入 #1

5 11
3 4 3 5 5

输出 #1

1 3 3

输入 #2

6 15
5 3 3 4 4 5

输出 #2

-1