Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Бактерии

(Время: 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.TXTOUTPUT.TXT
14 11
3 5 1 10
2 9 2 13
5
213 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

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

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


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 2021 / 2022
 2022 / 2023
 2023 / 2024
 A. Посадка в самолет
 B. Битоническая последовательность
 C. Игра с таблицей
 D. Выбор столицы
 E. Разбиение массива
 F. Бактерии
 G. Разбиение на тройки
 H. Обходы бинарного дерева

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru