헌터 곰 (Milk Sum) timer 4s memory 32MB

연어 사냥꾼의 마을의 N마리의 곰들은 각각의 정수값인 연어 수확량 a_1,…,a_N을 갖는다. 다시 말해, i번째 곰은 분당 a_i마리의 연어를 수확한다.

매일 아침 연어 사냥꾼의 마을의 촌장은 N마리의 곰들을 한 마리 씩 강에 보내서 연어를 사냥하게 한다.

첫 번째 곰은 1분간 사냥하고 돌아오고, 두 번째 곰은 1분이 추가된 2분간 사냥을 하고 돌아온다. 나머지 곰들은 마찬가지로 1분씩 점점 추가된 시간만큼 사냥을 한다.

즉, 처음 사냥을 나간 x번 곰은 a_x마리의 연어를 수확해오고, 두 번째 사냥을 나간 y번 곰은 2a_y마리의 연어를 수확해오고, 세 번째 사냥을 나간 z번 곰은 3a_z마리의 연어를 수확해온다.

가장 최적의 순서로 곰들을 사냥 보낸다면 총 T마리의 연어를 잡아오는 것이 가능하다고 한다.

연어 사냥꾼의 마을의 특이한 사냥법을 알게된 이웃 마을 곰은 특정 곰 i의 연어 수확량이 a_i에서 j로 바뀐다면 T가 어떻게 변할지 궁금해졌다.

그래서 이웃 마을 곰은 연어 사냥꾼의 마을의 촌장에게 찾아가 "i번 곰의 연어 수확량이 j로 바뀐다면 T는 어떻게 되나요?"라는 질문을 Q번 하였다.

연어 사냥꾼의 마을 촌장은 갑작스러운 질문에 대답을 못하고 있다. 우리가 대신 답해주는 프로그램을 만들어 연어 사냥꾼의 마을 촌장을 도와주자.