한컴이와 정올이는 IOI국으로 여행을 매년 간다.

또, 매년 갈때마다 기념품을 사고 돌아온다.

IOI국의 기념품 가게에는 총 N개의 기념품이 있으며, 각각의 가격은 c₁, c₂,...,c_N원이라고 한다.

i번째 해에, 한컴이와 정올이는 KOI국에 있을 친구들의 것까지 총 m_i개의 서로 다른 기념품을 사려고 한다.

하지만, 매번 기념품을 산 뒤 정산하기가 귀찮았던 한컴이는 정올이에게 다음과 같은 제안을 했다.

"가격이 k_i원 이하인 기념품은 내 돈으로 전부 살게. 하지만 k_i원보다 더 비싼 기념품은 내가 k_i원만 내주고,

나머지는 너가 사는게 어때? 아 대신 물건 정하는 것은 귀찮으니 내가 알아서 할게~~"

정올이는 돈 관리의 신이기 때문에, 이 제안이 과연 본인에게 이득이 될지 손해가 될지 고민해보기로 한다.

구체적으로 한컴이가 총 H원을 내고 정올이가 J원을 내면, H - J의 값의 최소값을 알아보아 만약 너무 작다면 이 제안을 거절할 것이다.

하지만 정올이는 동시에 수학을 잘 하지 못하기에 여러분의 도움을 받고자 한다.

N개의 기념품의 가격이 주어지고, Q년에 걸쳐 각 해마다 k_i와 m_i가 주어질 때, 각 해마다 H - J의 최소값을 구해주자.

기념품 timer 1초 memory 1024MB

기념품 1초 1024MB