Задача: Бактерии
В биологической лаборатории проводят эксперимент. В начале у ученых есть \(n\) замороженных бактерий, пронумерованных от \(1\) до \(n\).
Согласно плану эксперимента замороженная бактерия с номером \(i\) попадёт в чашку Петри через \(a_i\) секунд после начала эксперимента. Если таких бактерий несколько, они все попадают туда одновременно.
Как только замороженная бактерия оказывается в чашке Петри, она размораживается и начинает созревать. Созревание бактерии с номером \(i\) занимает \(t_i\) секунд. Как только бактерия созрела, она начинает размножаться: немедлено превращается в две созревшие бактерии, и затем каждая созревшая бактерия в конце каждой секунды снова делится на две созревшие бактерии.
Размером колонии называется общее количество бактерий в чашке Петри. Цель эксперимента — определить, через сколько секунд размер колонии будет в точности равен \(m\).
Помогите ученым определить искомое число секунд или выясните, что размер колонии никогда не будет в точности равен \(m\).
Формат входных данных
В первой строке даны целые числа \(n\), \(m\) (\(1 \le n \le 2 \cdot 10^5\), \(1 \le m \le 10^{9}\)) — количество замороженных бактерий и желаемый размер колонии.
Во второй строке даны \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^{9}\)) — времена перемещения замороженных бактерий в чашку Петри.
В третьей строке даны \(n\) целых чисел \(t_1, t_2, \ldots, t_n\) (\(1 \le t_i \le 10^{9}\)) — продолжительность созревания замороженных бактерий.
Формат выходных данных
Если размер колонии никогда не будет равен \(m\), выведите \(-1\).
В противном случае выведите число секунд после начала эксперимента, через которое размер колонии будет в точности равен \(m\).
Рассмотрим, как развивается эксперимент в первом примере.
| 0 |
заморожена |
заморожена |
заморожена |
заморожена |
0 |
| 1 |
заморожена |
заморожена |
в чашке Петри, созревает |
заморожена |
1 |
| 2 |
заморожена |
заморожена |
в чашке Петри, созревает |
заморожена |
1 |
| 3 |
в чашке Петри, созревает |
заморожена |
в чашке Петри, созрела, 2 бактерии |
заморожена |
3 |
| 4 |
в чашке Петри, созревает |
заморожена |
в чашке Петри, созрела, 4 бактерии |
заморожена |
5 |
| 5 |
в чашке Петри, созрела, 2 бактерии |
в чашке Петри, созревает |
в чашке Петри, созрела, 8 бактерий |
заморожена |
11 |
Ваш ответ: