E. Шатар

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бриан шатрыг хүндлэн биширдэг байлаа. Хэдхэн жилийн өмнө Стив түүнтэй шатрын морь бол ноёноос хамаагүй дээр дүрс гэж маргаж үүнийгээ батлахын тулд морь үнэхээр хурдан гэдгийг нотлон харуулахыг хүсэж байлаа.

Тэр Брианд зориулан хязгааргүй шатрын хөлөг бий болгоод бүүр сонирхолтой байлгахын тулд зарим нэг нүдийг устгажээ. Бриан морь ($0, 0$) нүднээс хөдлөөд $k$-ээс илүүгүй нүүгээд хүрч чадах нүдний тоог мэдэхийг хүсэж байлаа. Мэдээж устгагдсан нүдэн дээр нүүж очих хориотой.

Бриан тооцоолж үзэх гэсэн боловч Стив түүнээс аль хэдийн тооцоолох ажилдаа орсон байлаа. Брианд Стивээс хурдан тооцоолж олоход нь тусална уу.

Оролт

Эхний мөрөнд $k$, $n$ ($0 ≤ k ≤ 10^18, 0 ≤ n ≤ 440$) буюу морины нийт нүүдлийн тоо болон устгагдсан нүдний тоо.

Удаах $n$ мөрөнд устгагдсан нүдний координат ($x_i, y_i$) байрлана. ($|x_i| ≤ 10; |y_i| ≤ 10$) Бүх нүднүүд хоорондоо ялгаатай ба ($0, 0$) нүд устгагдаагүй байдлаар өгөгдөнө.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Гаралт

Хариу нэлээд урт тоо гарж болзошгүй тул $1000000007$-д хуваасан үлдэгдлийг хэвлэнэ.

Орчуулсан: gmunkhbaatarmn

Жишээ тэстүүд

Оролт
1 0
Гаралт
9
Оролт
2 7
-1 2
1 2
2 1
2 -1
1 -2
-1 -2
-2 -1
Гаралт
9
Сэтгэгдлүүдийг ачааллаж байна...