문제
ICT 생수회사에서는 길이가 N인 어떤 지역의 계곡에서 물을 길어다 물의 오염 정도에 따라 추가로 비용을 들여 정수를 하여 상품으로 판매한다. 계곡은 가장 상류를 기준으로 단위 길이로 나누어 각각의 위치마다 1부터 N까지 차례대로 번호를 부여하였다.
계곡에는 중간 중간 식당이나 팬션과 같은 시설들이 있어서 물을 오염시킨다. 오염을 시키는 범위는 그 시설의 종류에 따라 달라지며 어떤 시설에서 오염을 시키는 범위가 주어지면 그 시설부터 하류쪽으로 주어진 범위안에 있는 곳은 모두 오염이 된다. 예를 들어 5인 지점에 있는 시설에서 오염을 시키는 범위가 3이라면 5~7까지가 똑같이 오염이 되지만 8위치부터는 그 영향을 받지 않는다는 것이다. 물이 오염이 되면 오염의 정도에 따라 그 만큼의 비용을 들여서 정수를 해야 원래의 상태로 만들 수 있다.
계곡의 길이와 계곡을 오염시키는 각 시설의 정보를 입력받아서 오염이 가장 적은 위치를 출력하고 그 위치에서 물을 정수하여 상품으로 만들기 위한 비용, 즉 오염의 정도를 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 계곡의 길이 N과 오염을 시키는 시설의 수 M이 각각 자연수로 주어진다. ( 1 ≤ N ≤ 1,000,000,000, 1 ≤ M ≤ 100,000 ) 두 번째 줄부터 M개의 줄에는 각 시설의 위치(Si)와 그 시설부터 하류로 오염시키는 범위(Li), 오염의 정도(오염을 정수하는데 필요한 비용, Vi)가 각각 자연수로 주어진다.( 1 ≤ Si ≤ N, Li ≤ N-Si+1, 1 ≤ Vi ≤ 21,000 )
출력
오염이 가장 적은 물을 얻기 위한 위치와 그 위치에서 얻은 물을 정수하여 상품으로 만들기 위한 비용을 출력한다. 만약 비용이 같은 위치가 여럿이라면 상류에서 가장 가까운 곳을 출력한다.
예제
10 3
1 5 10
3 5 5
7 4 6
6 5
로그인해야 코드를 작성할 수 있어요.