cho.sh

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

아직 제출이 없습니다시간 제한5초메모리 제한1024 MB

문제

은규는 모바일 게임 “은하 온라인”을 출시하고 신규 유저를 확보하기 위해 마케팅 솔루션 제공 업체인 MOLOCO의 “몰로코 클라우드 DSP” 서비스를 이용하기로 했다. 이 서비스는 머신러닝 엔진을 중심으로 고객사의 광고와 마케팅을 최적화하며, 손쉬운 해외 진출 및 글로벌 마케팅을 지원해준다. 은규는 MOLOCO가 전 세계에서 가치 있는 유저를 타겟팅하여 광고를 내보내기 때문에 광고비 대비 많은 수의 유저를 유입시킬 수 있을 것이라 기대했다.

은규가 “은하 온라인” 광고를 내보낼 타겟 국가는 총 NN개이며, 각 국가에는 MM개의 도시가 있다. 편의상 국가는 11번부터 NN번까지 번호가 매겨져 있으며, 국가별로 도시들이 각각 11번부터 MM번까지 번호가 매겨져 있다. MOLOCO측의 도움으로 국가 ii의 도시 jj에 게임 광고를 내보냈을 때 유입될 유저의 수 a_i,j(1≤i≤Na\_{i,j}(1\le i\le N; 1≤j≤M)1\le j\le M)를 미리 예측하여 알 수 있었고, 이를 토대로 은규는 “은하 온라인” 마케팅 전략을 세우기 시작했다.

은규는 과도한 광고 노출로 게임의 평판이 나빠지지 않도록 각 국가별로 한 도시씩 골라 총 NN개의 도시에만 광고를 내보내기로 했다. 그리고 그중에서 한 도시를 골라 오프라인 이벤트를 개최해 최대 CC명의 신규 유저를 원하는 만큼 해당 도시에서 추가로 유입시키기로 했다. 즉, 원한다면 이벤트를 통해 신규 유저를 유입시키지 않을 수도 있다. 결과적으로 광고와 이벤트를 통해 게임에 유입시킨 유저 수의 총합이 목표량 PP 이상이어야 한다.

은규는 “은하 온라인”에 국가별 유저들을 최대한 균등하게 유입시키기를 원했기 때문에, “은하 온라인” 마케팅 전략으로 구성할 수 있는 모든 이벤트 및 NN개 도시 조합 중에서 불균등도가 가장 작은 조합으로 실제 마케팅을 진행하기로 했다. 불균등도는 국가별로 광고와 이벤트를 통해 유입될 유저 수들 중 최댓값과 최솟값의 차이로 정의된다.

은규는 게임에 유입시킬 유저 수의 총합의 목표량을 신중하게 설정하기 위해 QQ개의 목표량 후보를 선정했다. 그리고 각 목표량 후보 p_1,⋯ ,p_Qp\_{1},\cdots ,p\_{Q}에 따라 실제 마케팅을 진행할 조합의 불균등도를 모두 구해보기로 했다. 은규를 위해 이를 도와주자!

입력

첫 번째 줄에 세 정수 NN, MM, CC가 공백으로 구분되어 주어진다. (2≤N,M≤1,000(2\leq N,M\leq 1\\, 000; 0≤C≤109)0\leq C\leq 10^9)

1+i1+i 번째 줄에는 MM개의 정수 a_i,1,⋯ ,a_i,Ma\_{i,1},\cdots ,a\_{i,M}이 공백으로 구분되어 주어진다. (1≤i≤N(1\le i\le N; 1≤j≤M1\le j\le M; 0≤a_i,j≤109)0\leq a\_{i,j}\leq 10^9)

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

그 다음 줄부터 QQ개의 줄에 걸쳐, 각 목표량 후보를 나타내는 정수 p_1,⋯ ,p_Qp\_{1},\cdots ,p\_{Q}가 순서대로 주어진다. (1≤k≤Q(1\le k\le Q; 0≤p_k≤1018)0\leq p\_{k}\leq 10^{18})

출력

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

힌트

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