В Байтландии есть некоторое количество городов, соединённых дорогами с односторонним движением. К сожалению, состояние дорог оставляет желать лучшего, так что некоторые дороги являются непроходимыми для некоторых автомобилей. Более точно, для каждой дороги известен параметр — минимальная высота просвета для автомобиля, который может проехать по этой дороге. Некоторые дороги являются платными. Плата за проезд по такой дороге равна одному байтландскому тугрику. Также для каждой дороги известно время, которое автомобиль должен потратить, чтобы проехать эту дорогу.

Требуется найти, какая минимальная высота просвета может быть у автомобиля, на котором можно проехать из города s в город f не более, чем за t минут, потратив при этом не более b байтландских тугриков.

Первая строка входных данных содержит количество городов n (1 ≤ n ≤ 100), количество дорог m (1 ≤ m ≤ 10⁴), номер стартового города s и финишного города f (1 ≤ s, f ≤ n). Вторая строка содержит максимальную сумму денег, которую можно потратить, b (0 ≤ b ≤ 10⁶) и максимальное время на дорогу t (0 ≤ t ≤ 10⁶).

Каждая из последующих m строк имеет формат u_i v_i c_i t_i h_i, где u_i — город, в котором дорога начинается, v_i — город, в котором дорога заканчивается, c_i = 1, если дорога платная, и c_i = 0 в противном случае, t_i — это время, которое требуется для того, чтобы проехать по этой дороге, а h_i — минимальный дорожный просвет, требуемый для того, чтобы проехать по этой дороге (1 ≤ u_i, v_i ≤ n; 0 ≤ t_i ≤ 10⁴; 0 ≤ h_i ≤ 10⁶). Все числа во входных данных целые.

Если проехать из s в f, уложившись в ограничения по расходам и по времени, невозможно, выведите −1. Иначе в первой строке выведите минимальную высоту дорожного просвета автомобиля, при которой можно уложиться в ограничения, во второй — количество дорог в каком-либо маршруте, удовлетворяющем ограничениям, а в третьей — номера использованных дорог, перечисленные в порядке прохождения маршрута. Дороги занумерованы последовательными целыми числами от 1 до m в том порядке, в котором они заданы во входных данных.