Бактерии

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

Согласно плану эксперимента замороженная бактерия с номером i попадёт в чашку Петри через a_i секунд после начала эксперимента. Если таких бактерий несколько, они все попадают туда одновременно.

Как только замороженная бактерия оказывается в чашке Петри, она размораживается и начинает созревать. Созревание бактерии с номером i занимает t_i секунд. Как только бактерия созрела, она начинает размножаться: немедленно превращается в две созревшие бактерии, и затем каждая созревшая бактерия в конце каждой секунды снова делится на две созревшие бактерии.

Размером колонии называется общее количество бактерий в чашке Петри. Цель эксперимента – определить, через сколько секунд размер колонии впервые будет в точности равен m.

Помогите ученым определить искомое число секунд или выясните, что размер колонии никогда не будет в точности равен m.

Входные данные

В первой строке входного файла OUTPUT.TXT даны целые числа n, m (1 ≤ n ≤ 2×10⁵, 1 ≤ m ≤ 10⁹) – количество замороженных бактерий и желаемый размер колонии.

Во второй строке даны n целых чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹) – времена перемещения замороженных бактерий в чашку Петри.

В третьей строке даны n целых чисел t₁, t₂, ..., t_n (1 ≤ t_i ≤ 10⁹) – продолжительность созревания замороженных бактерий.

Выходные данные

В выходной файл OUTPUT.TXT выведите -1, если размер колонии никогда не будет равен m. В противном случае выведите число секунд после начала эксперимента, через которое размер колонии впервые будет в точности равен m.

Примеры

Замечание

Рассмотрим, как развивается эксперимент в первом примере.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]