B. Алхалтууд

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

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

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

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

Нэгэн өдөр Вася талбай уруу очтол тэнд түүний ямар ч найз байгаагүй бөгөөд түүнтэй "цохиод гүй" гэх тоглоомыг тоглох хэн ч байсангүй. Гэвч хөвгүүн урам зоригоо огтхон ч алдаагүй бөгөөд өөртэйгөө уг тоглоомыг тоглохоор болжээ. Та магадгүй "тэр яаж тоглосон юм бэ?" гэж асуух байх л даа. Гэхдээ хариулт нь тун энгийн юм.

Вася талбайг $n × m$ хэмжээ бүхий тэгш өнцөгт болохыг анзаарчээ. Тэгш өнцөгтийн нүднүүд нь $(x, y)$ ($1 ≤ x ≤ n, 1 ≤ y ≤ m$) гэсэн координатуудтай байх бөгөөд энд $x$ нь мөрийн дугаарыг $y$ нь баганын дугаарыг илэрхийлэх юм.

Анхандаа Вася ($x_{c}, y_{c}$) гэсэн координаттай нүдэн дээр зогсож байна. Тоглоомыг тоглохын тулд түүнд $k$ ширхэг 0-ээс ялгаатай урттай векторууд болох $(dx_{i}, dy_{i})$ өгөгдсөн байх ажээ. Тоглоом дараах байдлаар явагдана. Хөвгүүн бүх векторуудыг $1$-ээс $k$ хүртэлх дарааллын дагуу авч үзэх бөгөөд вектор болгоныг одоо хэрэглэгдэх вектор болгон авч үзсээр байх юм. Хөвгүүн одоо хэрэглэгдэх вектороо сонгосны дараагаар уг векторынхоо чиглэлийн дагуу боломжит хамгийн олон тооны зөвшөөрөгдсөн алхалт хийх юм (магадгүй тэрээр 0 тооны алхалт хийж ч болох юм).

Алхалт гэдэг нь хөвгүүний зогсож байгаа нүднээс одоо хэрэглэгдэх вектор-ийн чиглэлийн дагуу хийгдэх нэгэн шилжилт хөдөлгөөн юм. Өөрөөр хэлбэл Вася $(x, y)$ нүдэнд байрлах бөгөөд одоо хэрэглэгдэх вектор нь $(dx, dy)$ байвал нэг алхалт хийсний дараа Вася $(x + dx, y + dy)$ нүдэнд байрлах ажээ. Хэрэв хөвгүүн ямар нэгэн алхалтыг гүйцэтгэх явцад талбайгаас гадагш гарч явахгүй байвал уг алхалтыг зөвшөөрөгдсөн алхалт гэж нэрлэнэ.

Вася алхсаар алхсаар байх бөгөөд тэрээр өөрт өгөгдсөн бүх векторын дагуу алхсаны дараа зогсох юм. Тэрээр маш удаан хугацааны турш алхсан бөгөөд одоо тэрээр хэчнээн тооны алхалт хийснээ мартаж орхижээ. Тэгвэл хүүд туслан хэчнээн алхалт хийсэн болохыг нь тооцоолж өгнө үү.

Оролт

Оролтын эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($1 ≤ n, m ≤ 10^{9}$) өгөгдөх ба эдгээр нь талбайн хэмжээг илэрхийлнэ. 2-дахь мөрөнд бүхэл тоонууд $x_{c}$ болон $y_{c}$-ууд өгөгдөх ба эдгээр нь Вася-ын анх байрлаж буй нүдний координатуудыг илэрхийлнэ ($1 ≤ x_{c} ≤ n, 1 ≤ y_{c} ≤ m$).

3-дахь мөрөнд бүхэл тоо $k$ ($1 ≤ k ≤ 10^{4}$) өгөгдөх ба энэ нь нийт векторын тоог илэрхийлнэ. Дараагийн $k$ ширхэг мөрийн мөр болгонд 2 бүхэл тоо $dx_{i}$ болон $dy_{i}$ өгөгдөнө $(|dx_{i}|, |dy_{i}| ≤ 10^{9}, |dx| + |dy| ≥ 1)$.

Гаралт

Вася-ын хийсэн алхалтын тоог илэрхийлэх ганц бүхэл тоог хэвлэнэ үү.

С++ дээр 64-битийн бүхэл тоонуудыг унших болон бичихдээ %lld тодорхойлогчийг бүү хэрэглэнэ үү. Үүний оронд cin, cout streams болон %I64d тодорхойлогчдыг хэрэглэхийг илүүд үзнэ үү.

Орчуулсан: Баатархүү

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

Оролт
4 5
1 1
3
1 1
1 1
0 -2
Гаралт
4
Оролт
10 10
1 2
1
-1 0
Гаралт
0

Тэмдэглэл

Эхний жишээнд Вася-ын анхны байрлал нь $(1, 1)$ гэсэн нүдэн дээр байх бөгөөд эхний вектор $(1, 1)$-ын дагуу 3-н алхалт хийсэн байна. Ингэснээр тэрээр $(2, 2), (3, 3), (4, 4)$ гэсэн нүднүүдээр дараалан алхсан байх юм. Үүний дараа тэрээр 2-дахь вектор $(1, 1)$-ын дагуу 0 алхалт хийсэн байна. Учир нь тэрээр талбай нь захад ирсэн байгааг анхаарна уу. Дараа нь тэрээр 3-дахь вектор $(0,  - 2)$-ын дагуу дахин 1 алхалт хийх бөгөөд ингэснээр тэрээр $(4, 2)$ гэсэн нүдэнд алхалтаа дуусгах ажээ. Иймд Вася нийт $4$ алхалт хийсэн байна.

2-дахь жишээнд Вася-ын анхны байрлал нь $(1, 2)$ гэсэн нүдэн дээр байх бөгөөд тэрээр $( - 1, 0)$ гэсэн векторын дагуу $0$ алхалт хийсэн байна. Учир нь $(0, 2)$ координаттай нүд нь талбайн гадна байрлах юм.

Сэтгэгдлүүдийг ачааллаж байна...