버섯 채집

바이트나라 숲에는 여러 종류의 버섯이 자란다. 유명한 버섯 채집가 스타니스와프 씨는 최근 아주 맛있는 새 버섯 종을 발견하고 스타셰크라는 이름을 붙였다.

스타셰크는 하루에 무게가 얼마나 늘어나는지 쉽게 예측할 수 있다는 특징이 있다. 다만 모든 버섯은 일정한 날수가 지나면 독버섯이 되어 먹을 수 없게 된다. 스타니스와프 씨는 버섯을 보기만 해도 그 버섯이 며칠 뒤에 먹을 수 없게 되는지 알아낼 수 있다.

오늘 스타니스와프 씨는 숲에 가서 자신이 본 모든 버섯의 정보를 기록했다. 이제 그는 (무게 기준으로) 버섯을 가장 많이 딸 수 있으려면 며칠 뒤에 다시 숲에 와야 하는지 고민하고 있다. 똑같이 최선인 날이 여러 개라면 그는 항상 가장 이른 날을 고른다. 또한 아내가 하루에 두 번 숲에 가는 것을 금지했으므로, 그는 $0$일 뒤(즉 오늘)에 다시 올 수는 없다.

각 버섯 $i$는 오늘($0$일째) 무게가 $m_i$이고, 하루가 지날 때마다 무게가 $p_i$씩 늘어난다. 이 버섯은 오늘부터 세어 $d_i$일 동안, 즉 $0, 1, \dots, d_i - 1$일째에만 먹을 수 있고 $d_i$일째에 독버섯이 된다. 따라서 $t \ge 1$인 날 $t$에 스타니스와프 씨가 오면 $t < d_i$인 버섯만 먹을 수 있으며, 그때 그 버섯의 무게는 $m_i + p_i \cdot t$이다.

스타니스와프 씨는 다시 온 날에 먹을 수 있는 모든 버섯의 무게 합을 채집한다. 이 합을 최대로 만드는 날 $t \ge 1$을 구하여라. 그런 날이 여러 개라면 가장 이른 날을 답으로 한다.

첫째 줄에 버섯의 수 $n$ ($1 \le n \le 10^6$)이 주어진다.

이어지는 $n$개의 줄에 각 버섯의 정보가 한 줄에 하나씩 주어진다. 각 줄에는 공백으로 구분된 세 정수 $m$, $p$, $d$ ($1 \le m, p, d \le 10^5$)가 있으며, 각각 현재 무게, 하루당 무게 증가량, 그리고 그 버섯을 먹을 수 있는 날수를 뜻한다.

스타니스와프 씨가 버섯을 (무게 기준으로) 가장 많이 채집하려면 며칠 뒤에 다시 숲에 와야 하는지, 그 날수를 정수 하나로 한 줄에 출력한다. 최댓값이 여러 날에서 같다면 가장 이른 날을 출력한다.

버섯이 $(m, p, d) = (1, 1, 2)$, $(5, 5, 3)$, $(7, 2, 4)$ 세 개 있다고 하자. 다시 오는 날마다 먹을 수 있는 버섯의 무게 합은 다음과 같다.

• $1$일 뒤: 세 버섯의 무게는 각각 $(2, 10, 9)$이고 합은 $21$이다.
• $2$일 뒤: 첫 번째 버섯은 독버섯이 되어 먹을 수 없고, 남은 두 버섯의 무게는 $(15, 11)$, 합은 $26$이다.
• $3$일 뒤: 세 번째 버섯만 먹을 수 있고 그 무게는 $13$이다.
• $4$일 뒤: 먹을 수 있는 버섯이 하나도 없어 합은 $0$이다.

먹을 수 있는 버섯의 총무게는 $2$일 뒤에 $26$으로 가장 크므로 답은 $2$이다.