Tractor College

题意翻译

translated by @[RebelAlliance](https://www.luogu.org/space/show?uid=92461) ------------ 当大部分学生在准备考试时，拖拉机学院已经完成了夏季学期的期末考试。事实上，学生们只学一门科目——拖拉机驾驶的艺术，所以学期末学生们只有一个成绩，3分（合格），4分（良好），5分（优秀）。分数更低的，很不幸，会被开除。 学院有 $n$ 个学生，奇怪的是，每个人都拿的到奖学金。既然期末考试考完了，是时候决定下学期的奖学金数额了。 每个月的奖学金预算有 $s$ 卢布。为了更合理地分配奖学金，你必须遵守以下规则： • 考试成绩相同的学生拿相同的奖学金 • 用 $k_3, k_4, k_5$（卢布）分别表示拿3分、4分、5分的同学获得的奖学金数额。$k_3, k_4, k_5$ 是整数且满足 $0 \leqslant k_3 \leqslant k_4 \leqslant k_5$ • 定义 $c_3, c_4,c_5$ 分别表示拿3分、4分、5分的学生人数。每月的奖学金预算必须被花完，就是说，$c_3 \times k_3 + c_4 \times k_4 + c_5 \times k_5 = s$ • 引入函数 $f(k_3, k_4,k_5)=|c_3 \times k_3 - c_4 \times k_4| +|c_4 \times k_4 - c_5 \times k_5|$ ，其值表示奖学金分配的合理程度。在最佳分配方案中，$f(k_3, k_4,k_5)$ 取最小值 给出考试的结果和每月预算 $s$，请找出奖学金最佳分配方案 输入格式 第一行包括两个整数 $n$，$s$ （$3 \leqslant n \leqslant 300 , 1 \leqslant s \leqslant 3\times 10^5$） ——学生人数和每月奖学金预算。 第二行包括 $n$ 个整数，第 $i$ 个数表示第 $i$ 个学生在考试中的得分。保证每个成绩都有至少一名学生拿到。 输出格式 一行包括两个数 $k_3. k_4,k_5$，代表最佳分配方案。如果有多组答案，输出任意一组；如果没有答案，输出"-1"(输出不带引号）

题目描述

While most students still sit their exams, the tractor college has completed the summer exam session. In fact, students study only one subject at this college — the Art of Operating a Tractor. Therefore, at the end of a term a student gets only one mark, a three (satisfactory), a four (good) or a five (excellent). Those who score lower marks are unfortunately expelled. The college has $ n $ students, and oddly enough, each of them can be on scholarship. The size of the scholarships varies each term. Since the end-of-the-term exam has just ended, it's time to determine the size of the scholarship to the end of next term. The monthly budget for the scholarships of the Tractor college is $ s $ rubles. To distribute the budget optimally, you must follow these rules: - The students who received the same mark for the exam, should receive the same scholarship; - Let us denote the size of the scholarship (in roubles) for students who have received marks $ 3 $ , $ 4 $ and $ 5 $ for the exam, as $ k_{3} $ , $ k_{4} $ and $ k_{5} $ , respectively. The values $ k_{3} $ , $ k_{4} $ and $ k_{5} $ must be integers and satisfy the inequalities $ 0<=k_{3}<=k_{4}<=k_{5} $ ; - Let's assume that $ c_{3} $ , $ c_{4} $ , $ c_{5} $ show how many students received marks $ 3 $ , $ 4 $ and $ 5 $ for the exam, respectively. The budget of the scholarship should be fully spent on them, that is, $ c_{3}·k_{3}+c_{4}·k_{4}+c_{5}·k_{5}=s $ ; - Let's introduce function  — the value that shows how well the scholarships are distributed between students. In the optimal distribution function $ f(k_{3},k_{4},k_{5}) $ takes the minimum possible value. Given the results of the exam, and the budget size $ s $ , you have to find the optimal distribution of the scholarship.

输入输出格式

输入格式

The first line has two integers $ n $ , $ s $ ( $ 3<=n<=300,1<=s<=3·10^{5} $ ) — the number of students and the budget size for the scholarship, respectively. The second line contains $ n $ integers, where the $ i $ -th number represents the mark that the $ i $ -th student got for the exam. It is guaranteed that at each mark was given to at least one student.

输出格式

On a single line print three integers $ k_{3} $ , $ k_{4} $ and $ k_{5} $ — the sought values that represent the optimal distribution of the scholarships. If there are multiple optimal answers, print any of them. If there is no answer, print -1.

输入输出样例

输入样例 #1

5 11
3 4 3 5 5

输出样例 #1

1 3 3

输入样例 #2

6 15
5 3 3 4 4 5

输出样例 #2

-1