Бобр из Бобруйска строит плотину. Для постройки плотины Бобр таскает бревна из леса. В лесу есть $$$z$$$ деревьев. Из одного дерева получается одно бревно. Из $$$i$$$-го дерева получается бревно размеров $$$1$$$ на $$$z_i$$$. Брёвна резать нельзя. На то, чтобы срубить $$$i$$$-ое дерево уходит $$$t_i$$$ секунд. Плотина должна иметь 3 слоя и каждый слой длины $$$n$$$. Деревья находятся в лесу. Расстояние между плотиной и $$$i$$$-ым деревом равно $$$q_i$$$. Брёвна можно класть только горизонтально. Расстояние между деревьями задано списком рёбер с весами, где вес — количество метров между деревьями (граф не обязательно полный, но неориентированный, ходить бобру можно только по рёбрам). Бобр за раз может перенести не более 2 — ух брёвен. Его скорость передвижения — 1 метр в секунду. Нумерация с единицы.

Считайте что размер входных данных достаточно большой, и перебором эта задача не решается. Скиньте решения, я посмотрю на асимптотику и впишу размеры данных(так как у меня решения нет). В первой строке задано $$$z$$$ — количество деревьев. Во второй строке список длины $$$z$$$ — длины брёвен которые получается из деревьев. В третьей строке список длины $$$z$$$ — время на сгрызание деревьев. В четвертой строке вводится список длины $$$q$$$ — расстояние от платины до деревьев. В пятой строке вводится $$$n$$$ — длина слоёв. В шестой строке вводится $$$m$$$ — количество путей между деревьев. В следующих $$$m$$$ строках вводится по три числа: 2 номера деревьев и расстояние между ними в метрах.

Выведите w строк, в каждой строке выведите номера деревьев которые войдут в этот слой, бобр должен это сделать это за минимальное возможное время. Если плотину построить нельзя выведите -1.

Это вообще решабельно? Если нет, то напишите об этом.