# [Baltic2005]Trip

### 输入格式

The first line contains the integer numbers N (1<=N<=50,000), M (1<=M<=100,000), P ( 1<= P<= N), and T (0<=T<=1,000,000,000). The following M lines describe the bus routes. Each line contains the integer numbers si, ti, ai, bi, ci, di, where si and ti are the source and destination towns of the bus route i, and ai, bi, ci, di describe the departure and arrival times as explained above (1 <= si<=N, 1 <=ti<=N, 0<=ai<= bi < ci<=di<=1,000,000,000).

### 样例输入

```3 6 2 100
1 3 10 20 30 40
3 2 32 35 95 95
1 1 1 1 7 8
1 3 8 8 9 9
2 2 98 98 99 99
1 2 0 0 99 101
```

`32`

### 提示

The most pessimistic case for the optimal travel plan for the above example is as follows: Time Action 0…1 Wait in town 1 1…7 Take the bus line 3 from town 1 to town 1 7…8 Wait in town 1 8…9 Take the bus line 4 from town 1 to town 3 9…35 Wait in town 3 35…95 Take the bus line 2 from town 3 to town 2 95…98 Wait in town 2 98…99 Take the bus line 5 from town 2 to town 2 99…100 Wait in town 2 Total waiting time: 1+1+26+3+1=32