Loading [MathJax]/jax/output/SVG/jax.js

Республиканская олимпиада по информатике, 2011 год, 10-11 классы


Есеп A. Сиқырлы квест

Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайта

Сiз компьютерлiк ойынды ойнап отырсыз. Сiзде әр түрлi өлшемдi N сиқырлы заттар бар. Жол сөмкесiне өлшемдерiнiң қосындысы K-ға тең болатын заттар ғана салына алады. Әрқайсысы белгiлi күшi бар және берiлген заттардың белгiлi жиынтығын қолданатын M сыналаулар бар. Сапарға шығар алдында, сiз қолдана алатын сыналаулардың күштерiнiң қосындысы барынша көп болатындай етiп сөмкенi заттармен толтыруыңыз тиiс.
Формат входного файла
Енгiзу файлдың бiрiншi жолында үш бүтiн сан N, M, K берiледi (1N,M25, 1K109). Келесi жолда әрқайсысы 109-дан аспайтын, N бүтiн сандар — заттардың өлшемдерi берiледi. Келесi жолда әрқайсысы 109-дан аспайтын, M бүтiн сандар — сынаулардың күштерi берiледi. Келесi M жолдарда сынаулардың сипаттамалары, әр жолға бiреуден берiледi. Әр сынаудың сипаттамасы — қажет ететiн заттардың нөмiрлерiнiң тiзiмi. Әр сынау кемiнде бiр затты кажет етедi.
Формат выходного файла
Бiр жолды — өзiмен бiрге алатын заттардың нөмiрлерiнiң тiзiмiн шығарыңыз.
Примеры:
Вход
3 3 2
1 1 1
10 100 1000
1 2
1 2
3 2
Ответ
2 3
посмотреть в олимпиаде

Комментарий/решение: