Life on the great oceans has been good for captain Blackbeard and his fellow pirates. They have gathered so many treasures, that each of them is able to buy a house on their favorite island. The houses on this island are all placed in a long row along the beach line of the island. Next to a house, every pirate is also able to buy his own ship to do their own bit of plundering. However, this causes a whole new kind of problem.
Along the beach line there is a long pier where every pirate can park his ship. Although there is enough space along the pier for all the ships, not every pirate will be able to park in front of his house. A pirate is happy with his parking space if some part of the parking space is in front of the center of his house. Captain Blackbeard has been given the diffcult task of assigning the parking spaces to the pirates. A parking space for a pirate i is a range [ai, bi] (ai, bi∈R) along the pier such that li<= bi - ai, where li is the length of the ship of pirate i. Thus, pirate i is happy if ai <= xi <= bi, where xi is the center of the house of pirate i. Clearly, parking spaces of different pirates must be interior disjoint (the ends of ranges can coincide).
Above all, the captain wants a good parking space for himself, so he gives himself the parking space such that the center of his ship is aligned with the center of his house. Next to that, he wants to make as many pirates happy as possible. Can you help him out?