J. Компетенции
Задачу добавил: alef
Успешно сдано решений: 13
Министр экономики Калистрат тоже министру промышленности Силантию ответил. Что нет необходимости каждого жителя обязывать все существующие курсы проходить. Уже разработан для каждого рабочего места список компетенций, которыми должен владеть тот, кто место это занимает. Так что достаточно будет пройти учебные курсы, которые эти компетенции до нужного уровня поднимут. Кстати, чтобы жители царства не путались, каждый курс может изменить значения ровно двух компетенций.
Рабочее место, которое занимает уже знакомый нам слушатель Неонил, характеризуется двумя компетенциями, которые будем условно называть компетенцией $$$X$$$ и компетенцией $$$Y$$$. Неонил уже знает, что если он пройдёт курс, который позволит ему приобрести уровень компетенции $$$X$$$, равный $$$x$$$, а уровень компетенции $$$Y$$$ — равный $$$y$$$, он сможет продолжать занимать это рабочее место. В дальнейшем, ради простоты, будем использовать для обозначения курса, позволяющего приобрести уровень компетенции $$$X$$$, равный $$$x$$$, и уровень компетенции $$$Y$$$, равный $$$y$$$, пару $$$(x, y)$$$.
Но не всё так просто.
Во-первых, министерство науки издало постановление, согласно которому уровни всех компетенций всех жителей царства до прохождения каких-либо курсов считаются равными нулю.
Во-вторых, если житель царства проходит курс, описываемый парой $$$(x, y)$$$, то уровни его компетенций после прохождения этого курса считаются равными именно этим значениям, даже если одно или оба значения уровней компетенций до прохождения этого курса у жителя были больше.
В-третьих, министерство науки полагает, что резкий рост уровня компетенции невозможен. Поэтому, если житель пожелает пройти курс, описываемый парой $$$(x, y)$$$, он должен уже иметь уровни компетенций $$${\tilde x}$$$ и $$${\tilde y}$$$, такие, что $$$x - {\tilde x} \le d$$$ и $$$y - {\tilde y} \le d$$$, где $$$d$$$ — утверждённая постановлением министерства величина.
Неонил уже составил список курсов, которые могут изменить уровни компетенций $$$X$$$ и $$$Y$$$. Конечно, он хотел бы приобрести необходимый уровень компетенций, изучив как можно меньше курсов. Ваша задача — определить, какое минимальное количество курсов придётся изучить Неонилу, и какие это должны быть курсы.
В первой строке содержатся целые числа $$$n$$$ и $$$d$$$ $$$(1 \le n \le 1000, \, 1 \le d \le 10^5)$$$ — количество учебных курсов и величина, определяющая возможность изучения курса в зависимости от текущего уровня компетенций.
Во второй строке содержатся целые числа $$$x_1, x_2, \ldots, x_n$$$ $$$(0 \le x_j \le 10^9, \, j = 1, 2, \ldots, n)$$$, $$$x_j$$$ — значения уровней компетенции $$$X$$$, которое позволяет приобрести курс $$$\#j$$$.
В третьей строке содержатся целые числа $$$y_1, y_2, \ldots, y_n$$$ $$$(0 \le y_j \le 10^9, \, j = 1, 2, \ldots, n)$$$, $$$y_j$$$ — значения уровня компетенции $$$Y$$$, которое позволяет приобрести курс $$$\#j$$$.
Курс $$$\#1$$$ — это тот курс, который необходимо пройти Неонилу.
В первой строке выведите целое число — минимально возможное количество курсов, которое потребуется изучить Неонилу (включая курс $$$\#1$$$).
Во второй строке выведите номера курсов в том порядке, в котором их следует изучать Неонилу.
Если существует несколько возможных ответов, выведите любой из них.
Если ответа не существует, выведите единственное число $$$-1$$$.
6 5 15 15 5 0 0 5 10 10 5 8 7 5
4 2 6 4 1
3 5 10 10 5 0 0 5
-1
В первом примере Неонилу достаточно пройти 4 курса. У него есть две траектории обучения, окончанием которых будет курс $$$\#1$$$:
либо $$$3 \rightarrow 5 \rightarrow 4 \rightarrow 1$$$; в терминах компетенций $$$(0, 5) \rightarrow (5, 8) \rightarrow (10, 10) \rightarrow (15, 15)$$$;
либо $$$2 \rightarrow 6 \rightarrow 4 \rightarrow 1$$$; в терминах компетенций $$$(5, 0) \rightarrow (7, 5) \rightarrow (10, 10) \rightarrow (15, 15)$$$.
В качестве ответа можно вывести любую из последовательностей.
Во втором примере у Неонила нет возможности достичь необходимых значений компетенций. Поскольку изначальный уровень компетенций Неонила $$$(0, 0)$$$, то он может пройти только курсы $$$\#2$$$ и / или $$$\#3$$$ (в любом порядке). Однако после прохождения любого из них он не сможет перейти к изучению курса $$$\#1$$$ с компетенциями $$$(10, 10)$$$.