철수는 식물을 기르려고 한다.

1~100으로 번호가 매겨진 화분에 N개의 식물이 심어져있다.

i번째 식물은 si에서 시작하여 t_i로 끝나는 범위에 뿌리를 내리고 있으며 ci만큼의 물을 필요로한다.

철수에게는 M개의 자동분무기가 있고, i번째 자동분무기를 가동하는데 필요한 비용은 m_i이며, a_i에서 b_i까지 물을 p_i만큼 뿌린다.

물이 뿌려지는 위치는 겹칠 수도 있다.

철수를 위해 식물을 모두 잘 기르기 위해 필요한 최소 비용을 출력하시오.

자동분무기 (Air Cownditioning II) timer 1s memory 32MB

자동분무기 (Air Cownditioning II) 1s 32MB