필름 릴 균등 절단

문제

영화 보존소에서 낡은 필름 릴 N개를 잘라 전시용 프레임 조각을 만들려고 합니다.

각 릴은 오래 보관된 탓에 양쪽 끝이 손상되어 있습니다. i번 릴의 정보는 rolls[i] = [length, head, tail]로 주어지며

• length는 릴의 전체 길이(mm)
• head는 앞쪽 손상 구간의 길이, tail은 뒤쪽 손상 구간의 길이

입니다. 손상 구간은 반드시 잘라 버려야 하므로, i번 릴에서 실제로 쓸 수 있는 부분은 가운데의 length - head - tailmm 한 덩어리뿐입니다. 이 값이 0 이하인 릴은 통째로 폐기되어 조각을 하나도 만들 수 없습니다.

전시용 조각은 다음 조건을 지켜야 합니다.

• 모든 조각의 길이는 똑같아야 합니다.
• 영사기가 프레임 단위로만 돌아가므로, 조각의 길이는 unitmm의 양의 배수여야 합니다.
• 조각은 한 릴의 쓸 수 있는 구간 안에서만 잘라냅니다. 서로 다른 릴을 이어 붙일 수 없습니다.
• 자르고 남은 자투리는 버립니다.

조각을 need개 이상 확보할 수 있는 조각 길이 중 가장 긴 길이를 반환하는 solution(rolls, unit, need) 함수를 작성하세요. 어떤 길이로도 need개를 확보할 수 없다면 0을 반환합니다.

예시

rolls=[[100,5,5],[57,2,0],[40,10,6]], unit=4, need=6 → 24
  쓸 수 있는 길이는 각각 90, 55, 24mm.
  조각 길이 24mm(=4×6)로 자르면 3 + 2 + 1 = 6개로 딱 6개를 채웁니다.
  다음 배수인 28mm로는 3 + 1 + 0 = 4개뿐이라 부족합니다.
 
rolls=[[30,0,0]], unit=7, need=4 → 7
  손상이 없어 30mm를 전부 씁니다. 7mm 조각이면 4개(28mm 사용, 2mm 자투리),
  14mm 조각이면 2개뿐입니다.
 
rolls=[[10,4,4],[6,3,3]], unit=5, need=2 → 0
  쓸 수 있는 길이가 각각 2mm, 0mm라 5mm 조각조차 하나도 못 만듭니다.

제약 조건

• 1 ≤ rolls.length ≤ 100,000
• rolls[i]는 [length, head, tail] 형태의 길이 3짜리 배열입니다.
• 1 ≤ length ≤ 1,000,000,000, 0 ≤ head, 0 ≤ tail
• head + tail이 length보다 클 수 있습니다 (그 릴은 폐기).
• 1 ≤ unit ≤ 1,000,000,000
• 1 ≤ need ≤ 1,000,000,000
• 조각 길이 후보가 최대 10억 가지에 이르므로 1mm씩(또는 unit씩) 늘려 가며 확인하면 제한 시간 안에 끝나지 않습니다.
• 반환값은 정수입니다.

시간 복잡도 목표: O(N log(최대 길이 / unit))