14931번 - 물수제비 (SUJEBI)

급격한 기후변화로 최근 대곽나라의 많은 강에서 생태계 교란종이 나타나고 있다. 이에 대곽나라의 이기범 대통령은 국무회의를 주재해 정부 차원의 대책을 논의하게 되었다. 대통령, 국무총리, 환경부 장관은 물론 26부의 장관 및 차관이 모여 열띤 토론을 벌였다. 많은 좋은 의견이 나왔지만 그 중 단 한 계획만이 만장일치로 통과되었으니 일명 Flat Dumpling Plan (수제비 계획)으로, 강에서 돌로 물수제비를 해 여러 생태계 교란종을 맞춰 죽이는 계획이었다. 계획을 이행할 강의 강폭은 L(1 ≤ L ≤1,000,000)로 강을 L개의 연속한 칸으로 모델링할 수 있다. 환경부에서는 강의 1번 칸, 2번 칸, … L번 칸 각각에 살고 있는 생태계 교란종의 치명도에 따라 점수를 매겨 놨다. (고유종이 서식하는 곳도 있으므로 점수가 음수일 수도 있다.) 돌을 두 개 이상 던지기에는 팔이 아팠기에 오직 돌 하나로만 진행하기로 했다. 던져진 돌은 던진 파워에 따라서 일정 간격 d(1≤d≤L)로 뛴다. 즉, d번 칸, 2d번 칸, … [L/d]d번 칸을 지난다. 돌이 거친 칸들의 점수의 합을 최대로 하는 자연수 d를 찾아 정부에 보고하자.

첫째 줄에 강폭 L이 주어진다.

둘째 줄에는 L개 칸의 점수가 주어진다. 모든 점수는 -50,000 이상 50,000 이하의 정수이다.

점수를 최대로 하는 d 값과 그 때의 점수를 공백을 사이에 두고 출력한다. 만약 점수를 최대로 하는 d가 여럿 존재할 경우 가장 작은 d를 출력한다. 최대의 점수가 0 이하인 경우에는 계획을 시행하지 않는 것이 나으므로 0 0을 출력한다.