| Codeforces Round 398 (Div. 2) |
|---|
| Закончено |
Маленькая девочка Оля очень любит кефир. Каждый день она выпивает ровно k пакетов кефира, если их имеется хотя бы k, в противном случае — все, что есть. Но есть одна проблема: сроки годности. На каждом пакете написан день, позже которого этот пакет пить нельзя (ровно в этот день еще можно). Поэтому если в холодильнике у Оли в какой-то момент оказывается просроченный пакет, она его выкидывает.
Оля очень не любит выкидывать пакеты с кефиром, поэтому она применяет следующую стратегию: каждый раз, когда надо выпить очередной пакет, она выбирает тот, у которого срок годности заканчивается раньше всего. Несложно видеть, что эта стратегия минимизирует количество выкинутых пакетов и, в частности, позволяет обойтись без выкидывания, если это вообще возможно.
Но основная проблема, с которой столкнулась Оля, — это покупка нового кефира. Сейчас у Оли в холодильнике есть n пакетов кефира, про каждый известен его срок годности (через сколько дней он заканчивается). Оля пришла в магазин, и там есть m пакетов кефира, про каждый тоже известен его срок годности.
Определите, какое максимальное количество пакетов может купить Оля так, чтобы потом не пришлось ничего выбрасывать. Считайте, что Оля сегодня еще не пила ни одного пакета кефира.
В первой строке находятся три целых числа n, m, k (1 ≤ n, m ≤ 106, 1 ≤ k ≤ n + m) — число пакетов кефира у Оли в холодильнике, число пакетов кефира в магазине и сколько пакетов выпивает Оля каждый день.
Во второй строке находятся n целых чисел f1, f2, ..., fn (0 ≤ fi ≤ 107) — сроки годности пакетов кефира, которые уже есть у Оли в холодильнике. Срок годности выражается числом дней, на которые еще можно отложить употребление этого пакета. Таким образом, срок годности 0 означает, что пакет нужно выпить сегодня, 1 — что не позже завтра, и так далее.
Наконец, в третьей строке находятся m целых чисел s1, s2, ..., sm (0 ≤ si ≤ 107) — сроки годности пакетов, которые есть в магазине, в аналогичном формате.
Если в любом случае Оля не сможет выпить даже уже имеющиеся у нее пакеты, выведите ровно одно число -1.
Иначе в первой строке выведите максимальное количество пакетов x, которые Оля может купить так, чтобы ничего не выбрасывать. В следующей строке выведите ровно x чисел — номера пакетов, которые следует взять (пакеты нумеруются в том порядке, в котором они заданы во входном файле, начинается с 1). Естественно, числа не должны повторяться, однако могут идти в произвольном порядке. Если существует несколько подходящих наборов, разрешается вывести любой.
3 6 2
1 0 1
2 0 2 0 0 2
3
1 2 3
3 1 2
0 0 0
1
-1
2 1 2
0 1
0
1
1
В первом примере из условия k = 2 и дома у Оли есть три пакета со сроками годности 0, 1 и 1 (т. е. истекающими сегодня, завтра и завтра), а в магазине есть 3 пакета со сроком годности 0 и 3 пакета со сроком годности 2. Оля может купить три пакета, например, один со сроком годности 0 и два со сроком годности 2.
Во втором примере все три уже имеющихся пакета имеют срок годности, оканчивающийся сегодня, и поэтому Оля не успеет их выпить вне зависимости от того, возьмет ли она еще один пакет в магазине или нет.
В третьем примере сегодня Оля выпьет k = 2 пакета (один уже имеющийся и один из магазина), а завтра — оставшийся один пакет.
