22060번 - Освещение сцены 다국어

Для освещения сцены были установлены n прожекторов. Прожекторы стоят вдоль сцены и пронумерованы слева направо числами от 1 до n. Прожектор с номером i имеет мощность p_i.

Сцена будет считаться освещенной, если суммарная мощность включенных прожекторов не меньше Z. Ситуация осложняется тем, что каждый из работающих прожекторов должен быть подключен к определенному набору разъемов. Всего имеется k различных разъемов, i-й прожектор имеет k_i выходов и должен быть подключен к разъемам a_i,1, a_i,2, ..., a_i,ki. В каждый момент времени к разъему может быть подключено не более одного прожектора.

Место установки источника питания еще не определено. Чтобы оптимизировать процесс прокладки проводов, перед вами поставили следующую задачу: для каждого i от 1 до n найдите минимальное r_i, что среди прожекторов с номерами от i до r_i включительно можно выбрать подмножество одновременно работающих прожекторов так, что сцена будет освещена.

Первая строка содержит три целых числа n, k и Z (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 8, 1 ≤ Z ≤ 10⁹). Вторая строка содержит n целых чисел p₁, ..., p_n (1 ≤ p_i ≤ 10⁹). Следующие n строк содержат описание разъемов, к которым нужно подключать прожекторы, i-я из них содержит число k_i (1 ≤ k_i ≤ k), а также k_i различных чисел a_i,1, a_i,2, ..., a_i,ki (1 ≤ a_i,j ≤ k).

Выведите n строк: в i строке выведите число r_i, если такое существует, и −1 иначе.