시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB21150.000%

문제

A railway company just launched a new train prototype made out of a single railway wagon containing N chairs. Each chair is labelled from 1 to N (starting at the front of the train) and they are arranged in a row, one behind the other. The following rules must be followed by every passenger:

  1. Passengers must board the train only through the rear door which is located behind all seats. Once inside the train, passengers are only allowed to move towards the front of the cabin and may exit the train only through the front door (located in front of all seats).
  2. Each passenger must take the seat immediately behind the last occupied chair. If the train is fully empty, the passenger must take the front seat (labeled as seat 1).
  3. No passenger is allowed to leave their seat until disembarkment.
  4. At each train station, passengers that have reached their destination will exit the train. If there are passengers that are seated in front of a passenger that has reached his destination, they must also exit the train even if they have not reached their destination.
  5. Once a passenger exits the train, they will not be allowed to reboard.

Train route contains M stations, each labelled from 1 to M. The train will stop at each station, starting with station 1 and ending with station M. Across all M train platforms, there are a total of N passengers, labelled from 1 to N. The ticket price, as well as the boarding and destination stations are known in advance for each passenger.

The railway company wants to have only happy customers that reach their destination. In order to have only happy customers, the company allowed the conductor to choose which passengers can board and in which order they are allowed to do it. So, the conductor can choose to not allow certain passengers to board.

Find out what is the largest profit that the company can make having only happy customers, and also one valid ordering of embarkment that would yield this profit.

입력

The standard input contains the following input:

  1. the first line lists the pair of numbers N and M
  2. the following N lines list the travel requirement for each passenger x y c, such that x represents the boarding station, y represents the destination station and c is the ticket price.

Within each line, the numbers are positive integers and are separated by exactly one space.

출력

The standard output should have the following format:

  1. the first line should contain a number P representing the maximum amount of money that the railway company can make;
  2. the second line should contain a number Num representing the number of passengers that were able to reach their destination in an optimal solution, i.e. with the largest profit;
  3. the third line should contain the labels for each passenger that reached their destination, in boarding order, in this optimal solution. All passenger labels must be separated by exactly one space.

제한

  • 1 ≤ N ≤ 100000
  • 1 ≤ M ≤ 2·109
  • 1 ≤ x < y ≤ M for all passengers
  • 1 ≤ c ≤ 10000
  • Any passenger configuration that provides the maximum profit for the company will be considered correct;
  • For each test, you will be awarded 60% of the test points for printing the correct maximum profit P and 100% of the test points for printing all required output values;

서브태스크

번호배점제한
110

N ≤ 25

230

26 ≤ N ≤ 2500

360

2501 ≤ N ≤ 100000

예제 입력 1

4 8
2 6 10
4 5 1
3 7 10
1 7 10

예제 출력 1

20
2
1 3

A correct answer can be obtained as such:

  • station 2: passenger 1 boards the train
  • station 3: passenger 3 boards the train
  • station 6: passenger 1 exits the train
  • station 7: passenger 3 exits the train

예제 입력 2

4 10
1 3 3
1 10 2
2 5 3
1 2 5

예제 출력 2

11
3
4 1 3

A correct answer can be obtained as such:

  • station 1: passengers 4 and 1 board the train
  • station 2: passenger 4 exits the train passenger 3 boards the train
  • station 3: passenger 1 exits the train
  • station 5: passenger 3 exits the train 

채점 및 기타 정보

  • 예제는 채점하지 않는다.