18342번 - 순례의 시작 서브태스크스페셜 저지

그는 드디어 순례자가 되기로 결심했고, 이제 조금씩 순례의 시작을 위한 준비를 하며 성물을 모으고 있다. 왜냐하면, 신께서 이르시길, 순례자는 순례 도중에 반드시 서로 다른 여덟 개의 성물을 지니고 있어야 하기 때문이다.

성물에는 신의 힘이 깃들어 있어 순례 도중에 순례자가 지치지 않게 도와주지만, 그 자체에 무게가 있어 너무 무거우면 지니고 다니기 힘들다. 그래서, 선택한 여덟 성물에 깃든 신의 힘을 각각 $P_1, P_2, \cdots, P_8$이라고 하고, 무게를 각각 $W_1, W_2, \cdots, W_8$이라고 하면 $\frac{P_1+P_2+\cdots+P_8}{W_1+W_2+\cdots+W_8}$정도 순례가 편해진다.

그가 모은 성물이 모은 순서대로 주어질 때, 가진 성물이 하나씩 추가될 때마다, 가지고 있는 성물 중에서 정확히 여덟 개의 성물을 골랐을 때, 순례가 편해지는 정도의 최댓값을 구하여라.

첫 번째 줄에, 모은 성물의 개수를 의미하는 자연수 $N$이 주어진다.

다음 $N$ 개의 줄의 $i$ 번째 줄에, $i$ 번째로 모은 성물에 깃든 힘을 나타내는 자연수 $p_i$와 무게를 나타내는 자연수 $w_i$ ($1 \leq p_i, w_i \leq 10^6$)가 주어진다.

$N-7$ 개의 줄에 걸쳐 답을 출력한다. $i$ 번째 줄에는 $i+7$ 개의 성물을 모은 시점에 여덟 개의 성물을 골랐을 때, 순례가 편해지는 정도의 최댓값을 출력한다. 정답과의 절대오차 혹은 상대오차가 $10^{-9}$이하면 정답으로 인정한다.

• $8 \leq N \leq 20$

• $8 \leq N \leq 10^3$

• $8 \leq N \leq 10^4$