Задача №114283. Котлета
Аркадий хочет обедать. Он только что вернулся из магазина, где приобрел полуфабрикат — котлету, которую осталось только поджарить. Надпись на упаковке гласит, что котлету нужно жарить на сковороде на умеренном огне ровно 2 n секунд, причем сначала нужно ровно n секунд жарить котлету на одной стороне, а затем ровно n секунд — на другой. Аркадий уже нашел сковороду и зажег умеренный огонь, но тут осознал, что, возможно, у него не получится перевернуть котлету ровно через n секунд после начала готовки.
Аркадий слишком занят расстановкой по порядку наборов стикеров в своем любимом мессенджере, и может отвлечься на переворот котлеты только в определенные моменты времени. А именно, есть k промежутков времени, в которые он может это сделать, i -й из них — это отрезок времени с l i секунд от начала готовки до r i секунд до начала готовки, включительно. Аркадий решил, что не обязательно переворачивать котлету ровно в середине готовки, вместо этого, он перевернет ее несколько раз таким образом, чтобы суммарно котлета провела n секунд на одной стороне и n секунд на другой.
Помогите Аркадию, узнайте, может ли он выполнить свой план, если он может переворачивать котлету только в указанные отрезки времени, и если да, то какое минимальное число раз ему придется перевернуть котлету.
Первая строка содержит два целых числа n и k ( 1 ≤ n ≤ 500 000 , 1 ≤ k ≤ 100 ) — число секунд, которое котлета должна жариться с каждой из сторон, и число промежутков времени, когда Аркадий может ее переворачивать.
Следующие k строк содержат описания этих промежутков. Каждая строка содержит два целых числа l i и r i ( 0 ≤ l i ≤ r i ≤ 2· n ), что означает, что Аркадий может перевернуть котлету в любой момент времени, начиная с l i секунд от начала готовки и заканчивая r i секундами от начала готовки, включительно. В частности, если l i = r i , то Аркадий может перевернуть котлету в момент времени l i = r i . Гарантируется, что l i > r i - 1 для всех 2 ≤ i ≤ k .
Выведите в единственную строку « Hungry », если Аркадий не может пожарить котлету ровно n секунд на одной стороне и ровно n секунд на другой.
В противном случае, выведите в первую строку « Full », а во вторую — минимальное количество раз, которое ему необходимо перевернуть котлету.
Тесты, в которых в правильном ответе котлету нужно переворачивать не более двух раз, или Аркадий не может пожарить котлету требуемым образом, имеют суммарную стоимость не менее 30 баллов.
Тесты, в которых n ≤ 1000 , имеют суммарную стоимость не менее 40 баллов.
В первом примере котлету нужно перевернуть в моменты времени 3 секунды после начала и 13 секунд после начала.
Во втором примере котлету можно перевернуть, как и написано на упаковке, через 10 секунд после начала.
10 2 3 5 11 13
Full 2
10 3 3 5 9 10 11 13
Full 1
20 1 3 19
Hungry