시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 22 | 1 | 1 | 4.545% |
The subway in town X is a bit unusual. One train consists of a single wagon and there is a single row of L seats in it. If there are N passengers in the wagon, numbered from 0 to N-1, each passenger gets a certain amount of pleasure as follows:
For example let’s have 3 passengers in the wagon, numbered 0, 1 and 2, and A[0]=5, B[0]=2, A[1]=10, B[1]=1, A[2]=1, B[2]=1. Let the number of seats L=6 and consider the passengers sitting in the following schema: _ 0 _ _ 1 _ (“_” means an empty seat)
Passenger 2 is standing.
In this case:
The total pleasure of all the passengers is equal to 24.
Write program, which, given the number of seats L, the number of passengers N and the pleasure characteristics for each passenger, determines the maximum possible total pleasure for any number of seated passengers between 1 and N.
The first line of the standard input contains two integers – N and L - the number of passengers and the number of seats.
Each of the next N lines contains two non-negative integers – the characteristics А[i] and B[i] for passenger with index i.
Print N lines, the K-th of which contains a single number – the maximum total pleasure that the passengers can get if there are exactly K of them sitting.
(For K > L print 0, because there are no valid configurations of K passengers on L seats )
번호 | 배점 | 제한 |
---|---|---|
1 | 20 | 1 ≤ N ≤ 200 |
2 | 30 | 1 ≤ N ≤ 5000 |
3 | 50 | There are no additional constraints for the other test cases. |
3 2 1 2 3 4 5 6
11 8 0
For К = 2 the optimal configuration is: 1,2. Then passenger 1 gets pleasure 3, for being seated and 0*4, because there are no empty seats between him and the other passengers. Similarly, passenger 2 gets pleasure 5+0*6. Passenger 0 is standing so he gets pleasure 0. In total: 0 + (3+0*4) + (5+0*6) = 8.
3 3 1 2 3 4 5 100
205 112 9
For К = 1 the optimal configuration is: 2,_,_. The total pleasure is: 0 + 0 + (5+2*100) = 205