은하 온라인 마케팅 프로젝트

은규는 모바일 게임 "은하 온라인"을 출시했다. 신규 유저를 확보하기 위해 마케팅 솔루션 업체 MOLOCO의 "몰로코 클라우드 DSP" 서비스를 이용하기로 했다. 이 서비스는 머신러닝 엔진으로 고객사의 광고와 마케팅을 최적화하고, 해외 진출과 글로벌 마케팅을 지원한다. MOLOCO가 전 세계에서 가치 있는 유저를 골라 광고를 내보내므로, 은규는 광고비 대비 많은 유저를 유입시킬 수 있을 것이라 기대했다.

은규가 "은하 온라인" 광고를 내보낼 타겟 국가는 총 $N$개이고, 각 국가에는 $M$개의 도시가 있다. 편의상 국가는 1번부터 $N$번까지, 각 국가의 도시는 1번부터 $M$번까지 번호가 매겨져 있다. MOLOCO의 도움으로 국가 $i$의 도시 $j$에 광고를 내보냈을 때 유입될 유저 수 $a_{i,j}$($1\le i\le N$, $1\le j\le M$)를 미리 예측할 수 있었고, 은규는 이를 바탕으로 마케팅 전략을 세우기 시작했다.

은규는 과도한 광고 노출로 게임의 평판이 나빠지지 않도록 국가마다 도시를 한 곳씩 골라, 총 $N$개의 도시에만 광고를 내보내기로 했다. 그다음 그중 한 도시를 골라 오프라인 이벤트를 열고, 그 도시에 최대 $C$명의 신규 유저를 원하는 만큼 추가로 유입시키기로 했다. 이벤트를 열지 않을 수도 있다. 광고와 이벤트로 유입시킨 유저 수의 총합은 목표량 $P$ 이상이어야 한다.

은규는 국가별 유저 수를 최대한 고르게 맞추고 싶었다. 그래서 목표량을 달성할 수 있는 모든 이벤트 및 $N$개 도시 조합 가운데 불균등도가 가장 작은 조합으로 실제 마케팅을 진행하기로 했다. 불균등도는 국가별로 광고와 이벤트를 통해 유입될 유저 수 중 최댓값과 최솟값의 차이다.

은규는 목표량을 신중하게 정하려고 $Q$개의 후보 $p_1, \cdots, p_Q$를 골랐다. 각 후보에 대해 실제 마케팅을 진행할 조합의 불균등도를 구해 보려 한다. 은규를 도와주자.

첫 번째 줄에 세 정수 $N$, $M$, $C$가 공백으로 구분되어 주어진다. ($2\le N,M\le 1{,}000$, $0\le C\le 10^9$)

$1+i$번째 줄에는 $M$개의 정수 $a_{i,1}, \cdots, a_{i,M}$이 공백으로 구분되어 주어진다. ($1\le i\le N$, $1\le j\le M$, $0\le a_{i,j}\le 10^9$)

그다음 줄에 목표량 후보의 개수 $Q$가 주어진다. ($1\le Q\le 100{,}000$)

그다음 $Q$개의 줄에 걸쳐 각 목표량 후보 $p_1, \cdots, p_Q$가 순서대로 주어진다. ($1\le k\le Q$, $0\le p_k\le 10^{18}$)

$Q$개의 줄을 출력한다. $k$번째 줄에는 목표량 $p_k$를 만족하는 마케팅 전략의 최소 불균등도를 출력한다. 어떤 전략도 목표량을 달성하지 못하면 $-1$을 출력한다.

예제의 $p_1(=30)$에 대해, 국가별로 광고를 내보냈을 때 유입될 유저 수가 각각 3, 9, 6명인 도시를 고른다. 유입될 유저 수가 3명인 도시에서 오프라인 이벤트를 열어 추가로 12명을 유입시키면, 광고와 이벤트로 유입될 유저 수가 각각 15, 9, 6명이 된다. 이때 $p_1\le 15+9+6$을 만족하고 불균등도는 $15-6=9$가 된다.