02/04/2025 21:42:31

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

85. Китайская армия

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Китайский главнокомандующий решил подсчитать точное количество солдат в своей армии, пользуясь китайской теоремой об остатках. Он несколько раз расставлял солдат шеренгами по

$n$ человек и записывал количество человек в последней неполной шеренге. Известно, что количество солдат в китайской армии не меньше

$K$ . Используя эту информацию, определите минимально возможное количество солдат в китайской армии.

Ввод

Во входном файле в первой строке указаны два целых числа

$P$ и

$K$ , разделенные пробелом – число построений и минимально допустимое число солдат в китайской армии (

$1≤P≤19,\ 1≤K≤10^9$ ). Далее следует

$P$ строк, содержащих по два целых числа

$n$ и

$m$ , разделенных пробелом – количество человек в шеренге и количество человек в последней неполной шеренге или 0, если все шеренги полны (

$2≤n≤20,\ 0≤m<n$ ).

Вывод

В выходной файл вывести минимально возможное количество солдат в китайской армии.

Пример ввода

2 10
3 2
4 1

Пример вывода

05/05/2002	Региональная олимпиада Информатика-2002 (2)
21/09/2006	Практическое занятие 2 (C)
08/10/2011	Занятие 3 (B)
03/03/2015	Занятие 15 (B)