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

문제

은규는 모바일 게임 “은하 온라인”을 출시하고 신규 유저를 확보하기 위해 마케팅 솔루션 제공 업체인 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\leq N,M\leq 1,円 000$; 0ドル\leq C\leq 10^9)$

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

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

그 다음 줄부터 $Q$개의 줄에 걸쳐, 각 목표량 후보를 나타내는 정수 $p_{1},\cdots ,p_{Q}$가 순서대로 주어진다. $(1\le k\le Q$; 0ドル\leq p_{k}\leq 10^{18})$

출력

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

제한

노트

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