Nowadays spaceships are never launched from the Earth's surface. There is a huge spaceport placed in the
geostationary orbit and connected to the Earth with carbon nanotube cables. People and cargo are delivered to the
orbit by elevators moving along these cables. It turned out that the space elevator is much more comfortable and cheaper than a spaceship.
Tomorrow a group of key employees of the “Akross” corporation will go to
the spaceport with a secret mission. The spaceport management has
reserved a special double elevator for the group. The Head of
“Akross” demanded that at any given time the total importance of staff
in the elevator must not exceed some fixed value. Under this condition,
even in case of fatal accident the corporation will be able to recover.
Employees enter the elevator in turns. The elevator is sent up if
two people entered, or if only one person entered and the following person
behind him is so significant for the corporation that it is impossible to
send them together in one elevator.
The spaceport management wants to know the maximum number of elevator runs required to deliver all employees, so the right amount of oxygen cylinders and charged batteries can be prepared in advance.
Input
The first line contains integers n and s that are the amount of
employees of “Akross” assigned to the mission, and the maximum total
importance of two employees which can go together in the
elevator (1 ≤ n ≤ 105; 1 ≤ s ≤ 109).
The second line contains integers v1, …, vn that are the
importance of the employees (1 ≤ vi ≤ s).
Output
In the first line output the maximum amount of trips of the elevator. In
the second line output the importance of staff in order from the first
employee in the line to the last, for which the elevator will do this
amount of trips. If there are several possible answers, output any of
them.
Sample
input | output |
---|
6 6
1 2 3 3 4 5
| 5
2 5 1 3 4 3
|
Problem Author: Alex Samsonov
Problem Source: Ural Championship 2012