Отряд из x клонов пробрался на корабль "Звезда смерти", чтобы помочь Люку Скайуокеру в битве с Дартом Вейдером. Корабль состоит из n помещений и m двунаправленных переходов между ними. Клоны оказались в помещении 1 и планируют пробраться в помещение n, где находится Люк. Однако каждое помещение охраняется дроидами, i-е помещение охраняют a_i дроидов. При появлении в помещении повстанцев происходит сражение. Если численность отряда клонов больше численности отряда дроидов, то все дроиды будут убиты, а клоны не понесут потерь. В противном случае клоны также уничтожат всех дроидов, но потеряют половину состава: если в момент начала сражения было x клонов, то в конце останется x/2, округление вниз. Клонам придется сразиться с дроидами во всех помещениях, в которых они побывают, включая помещения 1 и n. Помогите командиру отряда понять, какое максимальное количество клонов сможет добраться из помещения 1 до помещения n.

Формат входных данных

В первой строке заданы два целых числа n и m - количество помещений и количество переходов на "Звезде смерти" (1 ⩽ n,m ⩽ 2 * 10⁵). В следующих m строках описаны переходы: i-й переход задаётся двумя целыми числами u_i и v_i - номерами помещений, которые соединяет переход (1 ⩽ u_i, v_i ⩽ n, u_i ≠ v_i). Гарантируется, что каждая пара помещений соединена не более чем одним переходом. На следующей строке записано целое число x - численность отряда клонов, пробравшихся на корабль (1 ⩽ x ⩽ 10⁹). В последней строке заданы n целых чисел a₁, a₂, ..., a_n - численности отрядов дроидов в помещениях (1 ⩽ a_i ⩽ 10⁹).

Формат выходных данных

Выведите единственное число - максимальное количество клонов, которые могут добраться до помещения n, начав движение из помещения 1. Если не существует маршрута, при движении по которому в живых останется хотя бы один клон, выведите 0.

Пример