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

Есеп 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 $(1 \le N,M \le 20,$ $1 \le K \le 10^9).$ Келесi жолда әрқайсысы $10^9$-дан аспайтын, $N$ бүтiн сандар — заттардың өлшемдерi берiледi. Келесi жолда әрқайсысы $10^9$-дан аспайтын, $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