Although Farmer John has no problems walking around the fair to collect prizes or see the shows, his cows are not in such good shape; a full day of walking around the fair leaves them exhausted. To help them enjoy the fair, FJ has arranged for a shuttle truck to take the cows from place to place in the fairgrounds.

FJ couldn't afford a really great shuttle, so the shuttle he rented traverses its route only once (!) and makes $N$ $(1 \le N \le 20,000)$ stops (conveniently numbered $1,\ldots,N$) along its path. A total of $K$ $(1 \le K \le 50,000)$ groups of cows conveniently numbered $1,\ldots,K$ wish to use the shuttle, each of the $M_{i}$ $(1 \le M_{i} \le N)$ cows in group $i$ wanting to ride from one stop $S_{i}$ $(1 \le S_{i} < E_{i})$ to another stop $E_{i}$ $(S_{i} < E_{i} \le N)$ farther along the route.

The shuttle might not be able to pick up an entire group of cows (since it has limited capacity) but can pick up partial groups as appropriate.

Given the capacity $C$ $(1 \le C \le 100)$ of the shuttle truck and the descriptions of the groups of cows that want to visit various sites at the fair, determine the maximum number of cows that can ride the shuttle during the fair.

Input

• Line 1: Three space-separated integers: $K$, $N$, and $C$
• Lines $2,\ldots,K+1$: Line $i+1$ describes group $i$ of the cows with three space-separated integers: $S_{i}$, $E_{i}$, and $M_{i}$

Output

• Line 1: The maximum number of cows that can ride the shuttle at the fair.

Examples

Input 1

8 15 3
1 5 2
13 14 1
5 8 3
8 14 2
14 15 1
9 12 1
12 15 2
4 6 1

Output 1

10

The shuttle can take 2 cows from stop 1 to stop 5, 3 from 5 to 8, 2 from 8 to 14, 1 from 9 to 12, 1 from 13 to 14, and 1 from 14 to 15.

Problem credits: Russ Cox and Hal Burch, 2006