تسمع Bessie عن زخة شهب استثنائية قادمة؛ ستصطدم بالأرض وتدمر كل ما تصيبه. قلقة على سلامتها، تقرر إيجاد طريق إلى مكان آمن لا يدمره أي شهاب أبدًا. ترعى الآن عند أصل المستوى الإحداثي وتريد الانتقال لمكان أكثر أمانًا مع تجنب الدمار في الطريق.
ستضرب $M$ شهب، $(1 \le M \le 50,000)$. الشهاب $i$ يصيب $(X_{i}, Y_{i})$، $(0 \le X_{i} \le 300; 0 \le Y_{i} \le 300)$، في الوقت $T_{i}$، $(0 \le T_{i} \le 1,000)$. يدمر النقطة وأربع نقاط شبكية مجاورة أفقيًا أو رأسيًا.
تغادر الأصل عند الوقت $0$ وتتحرك في الربع الأول موازية للمحاور بسرعة وحدة مسافة في الثانية إلى أي نقطة مجاورة لم تدمر بعد (غالبًا أربع). لا يمكنها الوجود عند نقطة في وقت تدميرها أو بعده.
حدد أقل وقت للوصول لمكان آمن.
الإدخال
اقرأ من الإدخال القياسي.
السطر $1$: عدد صحيح واحد $M$.
الأسطر $2,\ldots,M+1$: السطر $i+1$ يحتوي ثلاثة أعداد صحيحة مفصولة بمسافات: $X_{i}$ و$Y_{i}$ و$T_{i}$.
الإخراج
اكتب في الإخراج القياسي.
- السطر $1$: أقل وقت، أو $-1$ إذا استحال.
أمثلة
الإدخال 1
4 0 0 2 2 1 2 1 1 2 0 3 5
الإخراج 1
5
ملاحظة
تضرب أربعة شهب $(0, 0)$ و$(2, 1)$ و$(1, 1)$ و$(0, 3)$ في الأوقات $2$ و$2$ و$2$ و$5$ على الترتيب.
t = 0 t = 2 t = 5 5|. . . . . . . 5|. . . . . . . 5|. . . . . . . 4|. . . . . . . 4|. . . . . . . 4|# . . . . . . * = اصطدام شهاب 3|. . . . . . . 3|. . . . . . . 3|* # . . . . . 2|. . . . . . . 2|. # # . . . . 2|# # # . . . . # = مرعى مدمر 1|. . . . . . . 1|# * * # . . . 1|# # # # . . . 0|B . . . . . . 0|* # # . . . . 0|# # # . . . . -------------- -------------- -------------- 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6
في الرسم عند $t=5$ أقرب نقطة آمنة $(3, 0)$، لكن الشهاب الثاني يغلق الطريق إليها مبكرًا جدًا. التالية $(4,0)$ أيضًا تغلق مبكرًا. ثم نقاط القطر $(0,5)$-$(5,0)$. منها $(0,5)$ و$(1,4)$ و$(2,3)$ كلها يمكن بلوغها في $5$ وحدات زمن.
5|. . . . . . .
4|. . . . . . .
3|3 4 5 . . . . مواقع Bessie عبر الزمن
2|2 . . . . . . لأحد الحلول
1|1 . . . . . .
0|0 . . . . . .
--------------
0 1 2 3 4 5 6مؤلف المسألة: Jeffrey Wang، 2007