소들의 롤러코스터

소들이 롤러코스터를 만들고 있습니다. 소들은 예산을 넘기지 않으면서 가능한 한 재미있는 롤러코스터를 만들고 싶어 합니다.

트랙은 길이가 $L$인 하나의 직선 구간입니다. 서로 바꿔 쓸 수 있는 부품이 $N$개 있습니다. 부품 $i$의 길이는 $W_i$로 고정되어 있고, 지형 때문에 시작 위치 $X_i$에서만 설치할 수 있어 구간 $[X_i, X_i + W_i]$를 덮습니다. 소들은 롤러코스터가 위치 $0$에서 시작해 위치 $L$에서 끝나도록 부품들을 이어 붙이며, 마지막 부품을 제외한 각 부품의 끝은 바로 다음 부품의 시작과 정확히 맞닿아야 합니다. 즉, 선택한 부품들은 겹치거나 빈틈이 생기지 않도록 구간 $[0, L]$ 전체를 빈틈없이 덮어야 합니다.

각 부품 $i$에는 재미 점수 $F_i$와 비용 $C_i$가 있습니다. 롤러코스터의 총 재미는 사용한 부품들의 재미 점수의 합이고, 총 비용은 그 부품들의 비용의 합입니다. 전체 예산은 $B$입니다. 구간 $[0, L]$ 전체를 덮으면서 총 비용이 $B$ 이하인 롤러코스터의 최대 총 재미를 구하세요.

제약 조건

• $1 \le L \le 1000$
• $1 \le N \le 10000$
• $1 \le W_i \le L$
• $0 \le X_i \le L - W_i$
• $1 \le F_i \le 1000000$
• $1 \le C_i \le 1000$
• $1 \le B \le 1000$

• 첫째 줄: 공백으로 구분된 세 정수 $L$, $N$, $B$.
• $2 \dots N+1$번째 줄: $i+1$번째 줄에는 공백으로 구분된 네 정수 $X_i$, $W_i$, $F_i$, $C_i$가 주어집니다.

• 정수 하나: 예산을 넘기지 않으면서 트랙 $[0, L]$ 전체를 덮는 롤러코스터의 최대 총 재미를 출력합니다. 그런 롤러코스터를 만들 수 없으면 $-1$을 출력합니다.

첫 번째 테스트 케이스에서 가장 재미있는 구성 중 하나는 입력의 3번째, 5번째, 6번째 줄에 주어진 부품을 고르는 것입니다. 이 부품들은 구간 $[0, 5]$를 덮는 이어진 롤러코스터가 되며 총 재미는 $17$, 총 비용은 $7$로 예산 $10$ 이내입니다. 처음 두 부품을 고르면 재미는 더 커지지만($25$) 비용의 합이 $12$가 되어 예산을 초과합니다.