지우는 콘센트에 간단한 장치를 설치하여 절전형으로 만들었다. 지우는 이 콘센트를 통해 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) 전자제품은 먼저 작동시키는 순서대로 들어온다.

출력

입출력 예

입력

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 와트이다.

출처:functionx