#11908Skyscraper

The Build n' Profit construction company is about to build its tallest building. It will be huge, the tallest building in the world by a wide margin. It will house hundreds of thousands of people and have rocket-powered elevators to the upper floors. They even plan for a shuttle docking station instead of a helipad on its roof. But any building of that size is extremely costly to build and maintain, and even after selling and renting out all the floor-space it will be very difficult to meet the costs. Luckily, they have come up with a great solution. They will place advertisements on the outer walls of the building for a hefty charge. This will help offset some of the costs and bring in a profit.

However, feedbacks from prospective buyers of this advertisement space have brought up a new problem. Each customer wants a specific sized advertisement placed at a specific height, and they will pay a certain amount of money for it. Each advertisement order specifies its position (i.e. the lowest floor of the advertisement) and its size (i.e. the number of floors it covers, including the starting floor). Each advertisement spans the whole face of the building, so no two advertisements can occupy the same floor and no floors can be partially covered. Each order also includes the amount to be earned if that advertisement is placed on the building. Of course, no money is earned if only part of an advertisement is placed, or it is placed in any other position.

1
3
1 5 1
2 10 3
7 12 1

Case 1: 3