시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB94413852.055%

문제

서울과학고 매점에 드디어 두쫀쿠가 입고되었습니다! 매점 아저씨는 이 사실을 알리기 위해, 매점을 방문하는 $N$명의 학생에게 하루 동안 두쫀쿠 무료 나눔 이벤트를 하려고 합니다. 매점에서 고용할 수 있는 영업 사원은 총 $M$명 있으며, 각 영업 사원의 고용 여부는 자유롭게 정할 수 있습니다. $i$번째 영업 사원을 고용하면 $p_i$번째 학생부터 $q_i$번째 학생까지 각 학생마다 두쫀쿠를 $r_i$개씩 나누어 줍니다.

서울과학고 학생들은 두쫀쿠를 두 개씩 겹쳐 먹기 때문에, 홀수 개의 두쫀쿠를 나눠준다면 두쫀쿠 한 개를 더 구매하기 위해 매점에 다시 들를 것입니다. 매점 아저씨는 이 사실을 알고 $1$번 학생부터 $N$번 학생까지 모든 학생에게 홀수 개의 두쫀쿠를 나누어주려고 합니다. 매점 아저씨의 원대한 목표를 이루기 위해 매점에서 무료 나눔에 사용해야 하는 두쫀쿠의 총 개수의 최솟값을 계산하는 프로그램을 작성하세요.

입력

첫째 줄에 양의 정수 $N$과 $M$이 공백으로 구분되어 주어집니다.

둘째 줄부터 $M$개의 줄에 걸쳐 영업 사원들의 정보가 주어집니다. $i+1$번째 줄에 정수 $p_i$, $q_i$, $r_i$가 공백으로 구분되어 주어집니다.

출력

첫째 줄에 매점에서 무료 나눔에 사용해야 하는 두쫀쿠의 총 개수의 최솟값을 출력합니다. 만약 모든 학생에게 홀수 개의 두쫀쿠를 나눠줄 수 없다면 Dujjonku so expensive T.T를 출력합니다.

제한

  • $1\le N\le 100\, 000$
  • $1\le M\le 300\, 000$
  • $1\le p_{i}\le q_{i}\le N$ $(1\le i\le M)$
  • $1\le r_{i}\le 100\, 000$ $(1\le i\le M)$

서브태스크

번호배점제한
19

$N \le 4$

27

모든 $1 \leq i \leq M$에 대해 $p_i = q_i$

38

$p_1 < q_1 < p_2 < q_2 < \cdots < p_M < q_M$

428

$p_i < p_j \le q_i < q_j$를 만족하는 정수 $(i, j)$ 순서쌍이 존재하지 않습니다. ($1 \leq i, j \leq M$)

548

추가 제한 조건이 없습니다.

예제 입력 1

6 5
1 3 3
2 4 10
3 5 5
4 6 1
1 6 5

예제 출력 1

12

예제 입력 2

3 4
1 1 5
2 2 4
3 3 2
3 3 1

예제 출력 2

Dujjonku so expensive T.T

출처

School > 서울과학고등학교 > 2026 SciCom Qualification Test D번

채점 및 기타 정보

  • 예제는 채점하지 않는다.