Задача №114786. Отряд клонов
Отряд из \(x\) клонов пробрался на корабль «Звезда смерти», чтобы помочь Люку Скайуокеру в битве с Дартом Вейдером. Корабль состоит из \(n\) помещений и \(m\) двунаправленных переходов между ними. Клоны оказались в помещении 1 и планируют пробраться в помещение \(n\), где находится Люк.
Однако каждое помещение охраняется дроидами, \(i\)-е помещение охраняют \(a_i\) дроидов. При появлении в помещении повстанцев происходит сражение. Если численность отряда клонов больше численности отряда дроидов, то все дроиды будут убиты, а клоны не понесут потерь. В противном случае клоны также уничтожат всех дроидов, но потеряют половину состава: если в момент начала сражения было \(x\) клонов, то в конце останется \(\left \lfloor \frac{x}{2} \right \rfloor\), округление вниз. Клонам придется сразиться с дроидами во всех помещениях, в которых они побывают, включая помещения 1 и \(n\).
Помогите командиру отряда понять, какое максимальное количество клонов сможет добраться из помещения 1 до помещения \(n\).
В первой строке заданы два целых числа \(n\) и \(m\) — количество помещений и количество переходов на «Звезде смерти» (\(1 \le n, m \le 2 \cdot 10^5\)).
В следующих \(m\) строках описаны переходы: \(i\)-й переход задаётся двумя целыми числами \(u_i\) и \(v_i\) — номерами помещений, которые соединяет переход (\(1 \le u_i, v_i \le n\), \(u_i \neq v_i\)). Гарантируется, что каждая пара помещений соединена не более чем одним переходом.
На следующей строке записано целое число \(x\) — численность отряда клонов, пробравшихся на корабль (\(1 \le x \le 10^9\)).
В последней строке заданы \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) — численности отрядов дроидов в помещениях (\(1 \le a_i \le 10^9\)).
Выведите единственное число — максимальное количество клонов, которые могут добраться до помещения \(n\), начав движение из помещения 1. Если не существует маршрута, при движении по которому в живых останется хотя бы один клон, выведите 0.
4 4 1 2 1 3 2 4 3 4 7 10 2 3 1
3
4 4 1 2 1 3 2 4 3 4 7 10 3 3 1
0