Задача №115219. Бактерии
В биологической лаборатории проводят эксперимент. В начале у ученых есть \(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\).
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 13 | \(m \le n\), \(a_i \le 10^5\), \(t_i = 10^9\) | первая ошибка | |
| 2 | 14 | \(a_i = i\), \(t_i\) равны | первая ошибка | |
| 3 | 17 | \(n, a_i, t_i \le 3000\) | первая ошибка | |
| 4 | 23 | \(a_i\) равны \(1\) | первая ошибка | |
| 5 | 33 | — | 1–4 | первая ошибка |
Рассмотрим, как развивается эксперимент в первом примере.
| Время | Бактерия 1 | Бактерия 2 | Бактерия 3 | Бактерия 4 | Всего |
| 0 | заморожена | заморожена | заморожена | заморожена | 0 |
| 1 | заморожена | заморожена | в чашке Петри, созревает | заморожена | 1 |
| 2 | заморожена | заморожена | в чашке Петри, созревает | заморожена | 1 |
| 3 | в чашке Петри, созревает | заморожена | в чашке Петри, созрела, 2 бактерии | заморожена | 3 |
| 4 | в чашке Петри, созревает | заморожена | в чашке Петри, созрела, 4 бактерии | заморожена | 5 |
| 5 | в чашке Петри, созрела, 2 бактерии | в чашке Петри, созревает | в чашке Петри, созрела, 8 бактерий | заморожена | 11 |
4 11 3 5 1 10 2 9 2 13
5
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