91 - ZOJ Monthly, May 2010 - I
Nirvana is a country full of freedom. Its peace lies on the nuclear weapons. Association of Nuclear is an organization that develops and controls the nuclear weapons.
Recently, Nirvana was attacked by its greatest enemy, Guilt Federation of Warfare. Up to tens of thousands of people joined this wicked organization and they wanted to destroy the peaceful land. On the purpose of eliminating the protection, they decided to attack the buildings of Association of Nuclear first.
Yet Association of Nuclear got to know their plan. Even the smallest detail of the plan was acquainted. Various places would be attacked in different time in their plan. On the contrary, they had to send people to defense the attack. Limited by the number of available people, they might have to drop some of the building, however, because one person could not defense the enemy in two places at a time. In order to minimize the lost, can you help them make their defense plan?
There are no more than 20 test cases. For each test cases, the first line contains 3 integers N, M and P, indicating the number of places that was to be attacked, the time the attack would last and the number of people Assosiation of Nuclear had (0 < N, M <= 5000, 0 < P <= 100). The next N lines contains 3 integers each, t1, t2 and c, indicating the beginning time, the ending time of the attack and the cost made by the attack (0 < t1 <= t2 <= M, 0 <= c <= 100000). If there was not a person from Assosiation of Nuclear staying in the place to be attacked from t1 to t2, the attack would cause a lost of c to the organization. You can ignore the time for people traveling between two places. Three zeroes in one line indicating the end of the input.
For each test case, output the minimum lost to the organization in the first line. The next P lines output the mission numbers that assigns to the i-th people separated by one space in the i-th line. The missions are number from 1. Any assignment that can lead to the minimum lost can be acceptable. Output a blank line after each test case. DO NOT output trailing spaces or you may get "Wrong Answer".
2 5 1 1 2 10 2 3 20 2 5 1 1 2 10 3 4 20 2 5 2 1 2 10 2 3 20 0 0 0
10 2 0 1 2 0 1 2