베시는 농부 존의 수익성 좋은 새로운 AI 데이터 센터 사업인 CowWeave를 가동할 원자력 발전용 원자로를 설계하고 있다!

원자로의 노심에는 N개의 연료봉이 있으며(1 ≤ N ≤ 2×10^5), 1번부터 N번까지 번호가 매겨져 있다. i번째 연료봉은 “안정 동작 범위” [l_i, r_i] (−10^9 ≤ l_i ≤ r_i ≤ 10^9)를 가지는데, 이는 베시가 정하는 에너지 a_i가 l_i ≤ a_i ≤ r_i를 만족할 때에만 전력을 생산할 수 있다는 뜻이다. 그렇지 않으면 그 연료봉은 유휴 상태가 되어 전력을 생산하지 않는다. 또한 a_i는 항상 정수여야 한다. a_i는 [−10^9, 10^9] 범위로 제한되지 않으며, 어떤 정수라도 될 수 있음에 유의하라.

하지만 연료봉들 사이의 양자 상호작용 때문에, 원자로가 멜트다운(노심 용융)되지 않도록 베시는 (x, y, z) 형태의 제약 M개를 만족해야 한다. 각 제약은 a_x + a_y = z (1 ≤ x, y ≤ N, −10^9 ≤ z ≤ 10^9) 형태이다.

원자로가 멜트다운되지 않으면서, 전력을 생산하는 연료봉의 개수를 최대 몇 개까지 만들 수 있는지 구하는 일을 도와주어라!

#8844 upload 1 done 1 how_to_reg 1 call_split Subtarea

핵 원자로 timer 1s memory 1024MB

#8844
Subtarea

핵 원자로 1s 1024MB