Farmer John은 박람회를 걸으며 상을 받고 공연을 봐도 괜찮지만 소들은 하루 걸으면 지친다. 즐기도록 장소 사이를 옮겨 주는 셔틀 트럭을 마련했다.

좋은 차는 비싸서 빌린 차는 경로를 단 한 번 (!) 지나고 정류장 $N$개 ($1 \le N \le 20{,}000$), 번호 $1,\ldots,N$에 선다. 소 무리 $K$개 ($1 \le K \le 50{,}000$), 번호 $1,\ldots,K$가 타고 싶다. 무리 $i$의 $M_i$마리 ($1 \le M_i \le N$) 모두 $S_i$ ($1 \le S_i<E_i$)에서 이후 $E_i$ ($S_i<E_i\le N$)로 가려 한다.

정원 때문에 무리 전체를 태우지 못해도 일부는 태울 수 있다.

정원 $C$ ($1 \le C \le 100$)와 무리 설명으로 최대 탑승 소 수를 구하라.

입력

• 줄 $1$: 공백으로 구분한 정수 $K$, $N$, $C$.

• 줄 $2,\ldots,K+1$: 줄 $i+1$이 공백으로 구분한 정수 $S_i$, $E_i$, $M_i$로 무리 $i$를 설명한다.

출력

• 줄 $1$: 최대 탑승 소 수.

예제

입력 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

출력 1

10

참고

$2$마리를 $1$에서 $5$, $3$마리를 $5$에서 $8$, $2$마리를 $8$에서 $14$, $1$마리를 $9$에서 $12$, $1$마리를 $13$에서 $14$, $1$마리를 $14$에서 $15$로 태울 수 있다.

문제 출제: Russ Cox와 Hal Burch, 2006