ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5174: 伊利亚和文凭

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：1 通过：1
提交提交记录统计Web Board

题目描述



不久，一场信息学的学校奥林匹克竞赛将在伯兰举行，n名学生将参加。在奥林匹克竞赛评审团的一次会议上，决定根据结果，n名参赛者中的每一人都将获得一、二或三学位的文凭。因此，每个学生将获得一个文凭。他们还决定，必须给予至少min1和最多max1的第一学位文凭，至少min2和最多max2的第二学位文凭，以及至少min3和最多max3的第三学位文凭。经过一番讨论后，决定从分配满足这些限制的文凭的所有选项中选择最大限度地增加获得第一学位文凭的参与者人数的选项。在所有这些选项中，他们选择了最大限度地增加获得第二学位文凭的参与者人数的选项。如果这些选项有多个，他们会选择最大化第三学位文凭数量的选项。选择分发证书的最佳选项委托给了伊利亚，他是Berland最好的程序员之一。然而，他发现更重要的事情要做，所以你现在的任务是根据所描述的限制，选择分发文凭的最佳方案。可以保证，所描述的限制是这样的，即有一种方法可以选择这样一种分配文凭的选项，即所有n名奥林匹克竞赛的参与者都将获得某种学位的文凭。





Soon a school Olympiad in Informatics will be held in Berland, n schoolchildren will participate there.
At a meeting of the jury of the Olympiad it was decided that each of the n participants, depending on the results, will get a diploma of the first, second or third degree. Thus, each student will receive exactly one diploma.
They also decided that there must be given at least min1 and at most max1 diplomas of the first degree, at least min2 and at most max2 diplomas of the second degree, and at least min3 and at most max3 diplomas of the third degree.
After some discussion it was decided to choose from all the options of distributing diplomas satisfying these limitations the one that maximizes the number of participants who receive diplomas of the first degree. Of all these options they select the one which maximizes the number of the participants who receive diplomas of the second degree. If there are multiple of these options, they select the option that maximizes the number of diplomas of the third degree.
Choosing the best option of distributing certificates was entrusted to Ilya, one of the best programmers of Berland. However, he found more important things to do, so it is your task now to choose the best option of distributing of diplomas, based on the described limitations.
It is guaranteed that the described limitations are such that there is a way to choose such an option of distributing diplomas that all n participants of the Olympiad will receive a diploma of some degree.
Input
The first line of the input contains a single integer n (3≤n≤3·106)−the number of schoolchildren who will participate in the Olympiad.
The next line of the input contains two integers min1 and max1 (1≤min1≤max1≤106)−the minimum and maximum limits on the number of diplomas of the first degree that can be distributed.
The third line of the input contains two integers min2 and max2 (1≤min2≤max2≤106)−the minimum and maximum limits on the number of diplomas of the second degree that can be distributed.
The next line of the input contains two integers min3 and max3 (1≤min3≤max3≤106)−the minimum and maximum limits on the number of diplomas of the third degree that can be distributed.
It is guaranteed that min1+min2+min3≤n≤max1+max2+max3.
Output
In the first line of the output print three numbers, showing how many diplomas of the first, second and third degree will be given to students in the optimal variant of distributing diplomas.
The optimal variant of distributing diplomas is the one that maximizes the number of students who receive diplomas of the first degree. Of all the suitable options, the best one is the one which maximizes the number of participants who receive diplomas of the second degree. If there are several of these options, the best one is the one that maximizes the number of diplomas of the third degree.
Examples
Input 
6
1 5
2 6
3 7
Output 
1 2 3
Input 
10
1 2
1 3
1 5
Output 
2 3 5
Input 
6
1 3
2 2
2 2
Output 
2 2 2

输入格式

输入的第一行包含一个整数n（3≤n≤3·10^6）——将参加奥运会的学童人数。输入的第二行包含两个整数min1和max1（1≤min1≤max1≤10^6）——可以分配的第一学位文凭数量的最小和最大限制。输入的第三行包含两个整数min2和max2（1≤min2≤max2≤10^6）——可以分配的第二学位文凭数量的最小和最大限制。

输入的第三行包含两个整数min3和max3（1≤min3≤max3≤10^6）——上的最小和最大限制可以分配的第三学位文凭的数量。保证min1+min2+min3≤n≤max1+max2+max3。

输出格式

在输出的第一行输出三个数字，显示在分配文凭的最佳变体中，将向学生颁发多少第一、第二和第三学位的文凭。分配文凭的最佳方案是使获得第一学位文凭的学生人数最大化。在所有合适的选择中，最好的选择是最大限度地增加获得第二学位文凭的参与者人数。如果有几个这样的选择，最好的一个是最大限度地增加第三学位文凭的数量



Examples
Input 
6
1 5
2 6
3 7
Output 
1 2 3
Input 
10
1 2
1 3
1 5
Output 
2 3 5
Input 
6
1 3
2 2
2 2
Output 
2 2 2

分析：

 

首先在满足二三等奖最少数量的情况下去求出一等奖的最多数量，然后在满足三等奖最少数量的情况下去求出二等奖的数量，三等奖的数量用总量减去一二等的数量即可

输入样例 复制 

6
1 5
2 6
3 7

输出样例 复制 

1 2 3

分类标签