세차장
시간 제한5초메모리 제한512 MB
n개의 세차장마다 가격을 정해 총수익을 최대화하는 문제입니다. 고객은 구간 안에서 가장 싼 세차장을 고르며, 예산 안에 들어올 때만 이용합니다.
문제
Byteasar는 Byteotia의 주요 고속도로를 따라 세차장 n개를 운영하는 사업의 입찰에 참여하려고 한다. 입찰하기 전에 그는 얻을 수 있는 수익을 먼저 가늠하고 싶어 한다.
이를 위해 시장 조사를 의뢰했다. 조사 결과 m명의 잠재 고객이 이 도로를 지나갈 것으로 나타났다. i번째 고객은 세차장 a_i와 b_i 사이 구간(양 끝 포함)을 지나가며, 가격이 c_i바이thaler 이하라면 세차를 맡길 의향이 있다. Byteasar는 각 세차장의 가격을 서로 독립적으로 정한다. 각 고객은 합리적이고 깔끔한 에이전트여서, 자기 경로에 있는 세차장 중 가장 싼 곳을 고른다. 모든 세차장이 예산을 넘으면 세차하지 않는다. Byteasar는 총수익이 최대가 되도록 가격을 정하려고 한다.
입력
첫 줄에 세차장 수 n과 고객 수 m이 공백 하나로 구분되어 주어진다(1 ≤ n ≤ 50, 1 ≤ m ≤ 4000). 세차장은 1번부터 n번까지 번호가 붙어 있다. 이어지는 m개의 줄은 고객을 나타낸다. i번째 줄에는 정수 a_i, b_i, c_i가 공백으로 구분되어 주어진다(1 ≤ a_i ≤ b_i ≤ n, 1 ≤ c_i ≤ 500000). 이는 i번째 고객이 세차장 a_i에서 b_i까지 이동하며, 예산이 c_i바이thaler라는 뜻이다.
전체 점수의 75%에 해당하는 테스트에서는 m ≤ 250 조건이 추가로 성립한다.
출력
첫 줄에는 Byteasar의 최대 총수익 s를 바이thaler 단위로 정수 하나를 출력한다. 둘째 줄에는 합리적인 에이전트 가정 아래에서 수익 s를 얻는 가격표 p_1, p_2, ..., p_n을 공백으로 구분하여 출력한다. p_i는 i번째 세차장의 가격이며 1 ≤ p_i ≤ 500000을 만족해야 한다. 정답이 여러 개라면 그중 아무거나 골라도 된다.