В биологической лаборатории проводят эксперимент. В начале у ученых есть \(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 |
Примеры
| № | Входные данные | Выходные данные |
|
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
|