예열이 필요한 프린터 배치 출력

문제

시제품 공방에는 성능이 서로 다른 3D 프린터 N대가 있습니다. 모든 프린터는 시각 0에 동시에 전원이 켜지고, 켜진 뒤 예열 이 끝나야 출력을 시작할 수 있습니다.

i번 프린터는

• preheat[i]분 동안 예열합니다. 예열 중에는 아무것도 만들지 못합니다.
• 예열이 끝난 뒤부터는 부품 하나를 만드는 데 perUnit[i]분씩 걸리며, 쉬지 않고 계속 반복합니다.
• 부품은 완성된 것만 개수에 넣습니다. 만드는 중인 부품은 세지 않습니다.

즉 시각 t에 i번 프린터가 완성해 둔 부품 수는 t > preheat[i]이면 floor((t - preheat[i]) / perUnit[i]), 그렇지 않으면 0입니다.

모든 프린터가 만든 부품을 합쳐 target개 이상 이 되는 가장 이른 시각을 반환하는 solution(preheat, perUnit, target) 함수를 작성하세요. 반환값의 단위는 분입니다.

예시

preheat=[0,0], perUnit=[3,5], target=4 → 9
  시각 8: 0번 2개(6분·3분 소요분) + 1번 1개 = 3개 → 부족
  시각 9: 0번 3개 + 1번 1개 = 4개 → 달성
 
preheat=[10,2], perUnit=[1,7], target=5 → 14
  0번은 시각 10부터 1분에 1개, 1번은 시각 2부터 7분에 1개.
  시각 13: 0번 3개 + 1번 1개 = 4개 → 부족
  시각 14: 0번 4개 + 1번 1개 = 5개 → 달성
 
preheat=[7,7,7], perUnit=[2,2,2], target=10 → 15
  시각 14에는 프린터마다 3개씩 총 9개로 부족하고,
  시각 15에 4개씩 총 12개가 되어 처음으로 10개를 넘어섭니다.

제약 조건

• preheat.length == perUnit.length == N, 1 ≤ N ≤ 100,000
• 0 ≤ preheat[i] ≤ 1,000,000,000
• 1 ≤ perUnit[i] ≤ 1,000,000
• 1 ≤ target ≤ 1,000,000,000
• 정답은 최대 약 10^15분까지 커질 수 있으므로 시각을 1분씩 증가시키며 확인하면 제한 시간 안에 끝나지 않습니다.
• 반환값은 정수입니다.

시간 복잡도 목표: O(N log(최대 시각))