문제
진수는 콘센트에 간단한 장치를 설치하여 절전형으로 만들었다.
진수는 이 콘센트를 통해 N개의 전자제품을 작동시키려고 한다. 각 전자제품은 Ak초부터 작동을 시작하여 Bk초까지 작동을 시킬 것이다.
각 전자제품은 작동할 때에는 1초당 Ck 와트만큼의 전력이 소모되며, 작동하지 않을 때에는 1초당 Sk 와트만큼의 대기전력이 소모된다.
진수는 플러그를 빼기 귀찮아하기 때문에 새로운 전자제품의 플러그를 꼽을 때 이외에는 플러그를 빼지 않는다.
한편, 콘센트가 절전형이기 때문에 T초만큼 대기 전력 소모가 감지된다면 아예 전기를 차단하여 전력을 소모하지 않는다. 그러다가 전자제품이 작동되면 다시 전기가 공급된다.
진수가 N개의 전자제품을 사용할 계획이 주어질 때, 진수가 소모한 총 전력량을 구하는 프로그램을 작성하여라.
단, 한 번에 작동할 수 있는 전자제품은 최대 1개이다. 즉, 전자제품 작동 시간이 서로 겹치지 않는다.
입력
첫 번째 줄에는 전자제품의 수 N과 전기 차단 시간 T가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ T ≤ 1,000,000)
두 번째 줄부터 N개의 줄에는 각 전자제품의 작동을 시작하는 시각 Ak, 작동을 끝내는 시각 Bk, 소모전력 Ck, 대기전력 Sk 가 주어진다. (0 ≤ Ak < Bk ≤ 1,000,000, 1 ≤ Sk ≤ Ck ≤ 1,000)< 먼저 작동하는 전자제품이 먼저 들어온다.
출력
진수가 N개의 전자제품을 모두 사용한 후 소모된 전력을 출력한다. 이 값은 가장 마지막 전자제품을 사용한 후 소모하는 대기전력을 포함한다.
예제
4 3
0 2 10 1
7 13 57 3
15 16 23 8
36 46 30 12
754
0~2초 : 1번 전자제품을 사용하면서 10 × 2 = 20와트의 전력을 소모한다.
2~5초 : 1번 전자제품이 1 × 3 = 3와트의 대기전력을 소모한다.
5~7초 : 전기가 공급되지 않아 전력을 소모하지 않는다.
7~13초 : 2번 전자제품을 사용하면서 57 × 6 = 342와트의 전력을 소모한다.
13~15초 : 2번 전자제품이 3 × 2 = 6와트의 대기전력을 소모한다.
15~16초 : 3번 전자제품을 사용하면서 23 × 1 = 23와트의 전력을 소모한다.
16~19초 : 3번 전자제품이 8 × 3 = 24와트의 대기전력을 소모한다.
19~36초 : 전기가 공급되지 않아 전력을 소모하지 않는다.
36~46초 : 4번 전자제품을 사용하면서 30 × 10 = 300와트의 전력을 소모한다.
46~49초 : 4번 전자제품이 12 × 3 = 36와트의 대기전력을 소모한다.
49초~ : 전기가 공급되지 않아 전력을 소모하지 않는다. 소모된 전력은 20 + 3 + 342 + 6 + 23 + 24 + 300 + 36 = 754 와트이다.
로그인해야 코드를 작성할 수 있어요.