|
Бактерии
(Время: 2 сек. Память: 64 Мб Сложность: 36%)
В биологической лаборатории проводят эксперимент. В начале у ученых есть n замороженных бактерий, пронумерованных от 1 до n.
Согласно плану эксперимента замороженная бактерия с номером i попадёт в чашку Петри через ai секунд после начала эксперимента. Если таких бактерий несколько, они все попадают туда одновременно.
Как только замороженная бактерия оказывается в чашке Петри, она размораживается и начинает созревать. Созревание бактерии с номером i занимает ti секунд. Как только бактерия созрела, она начинает размножаться: немедленно превращается в две созревшие бактерии, и затем каждая созревшая бактерия в конце каждой секунды снова делится на две созревшие бактерии.
Размером колонии называется общее количество бактерий в чашке Петри. Цель эксперимента – определить, через сколько секунд размер колонии впервые будет в точности равен m.
Помогите ученым определить искомое число секунд или выясните, что размер колонии никогда не будет в точности равен m.
Входные данные
В первой строке входного файла OUTPUT.TXT даны целые числа n, m (1 ≤ n ≤ 2×105, 1 ≤ m ≤ 109) – количество замороженных бактерий и желаемый размер колонии.
Во второй строке даны n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109) – времена перемещения замороженных бактерий в чашку Петри.
В третьей строке даны n целых чисел t1, t2, ..., tn (1 ≤ ti ≤ 109) – продолжительность созревания замороженных бактерий.
Выходные данные
В выходной файл OUTPUT.TXT выведите -1, если размер колонии никогда не будет равен m. В противном случае выведите число секунд после начала эксперимента, через которое размер колонии впервые будет в точности равен m.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 4 11 3 5 1 10 2 9 2 13 | 5 |
2 | 13 124 5 6 8 8 1 6 4 6 4 7 10 3 9 5 2 10 5 2 1 1 4 8 3 4 1 9
| 8 |
Замечание
Рассмотрим, как развивается эксперимент в первом примере.
Время | Бактерия 1 | Бактерия 2 | Бактерия 3 | Бактерия 4 | Всего |
0 | заморожена | заморожена | заморожена | заморожена | 0 |
1 | заморожена | заморожена | в чашке Петри,
созревает | заморожена | 1 |
2 | заморожена | заморожена | в чашке Петри,
созревает | заморожена | 1 |
3 | в чашке Петри,
созревает | заморожена | в чашке Петри,
созрела,
2 бактерии | заморожена | 3 |
4 | в чашке Петри,
созревает | заморожена | в чашке Петри,
созрела,
4 бактерии | заморожена | 5 |
5 | в чашке Петри,
созрела, 2 бактерии | в чашке Петри,
созревает | в чашке Петри,
созрела,
8 бактерий | заморожена | 11 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |