جاذبية & quot؛ متاهة المعرفة & quot؛ تم بناؤها في مدرسة الكمبيوتر الصيفية (LCS). تتكون المتاهة من عدد N غرف ، مرقمة من 1 إلى N ، وبعضها به أبواب بينها. عندما يمر شخص من باب ، يتغير مؤشر معرفته بمقدار معين محدد لهذا الباب. مدخل المتاهة في الغرفة 1 ، المخرج & ndash؛ في الغرفة N. كل طالب يمر عبر المتاهة مرة واحدة بالضبط وينضم إلى مجموعة دراسة أو أخرى اعتمادًا على مقدار المعرفة المكتسبة (عند دخول المتاهة ، يكون هذا المؤشر صفرًا). مهمتك هي إظهار أفضل نتيجة.
& nbsp؛
الإدخال:
يحتوي السطر الأول من الإدخال على أعداد صحيحة N (1 & lt؛ = N & lt؛ = 2000) & ndash؛ عدد الغرف و M (1 & lt ؛ = M & lt ؛ = 10000) & ndash؛ عدد الأبواب. يحتوي كل سطر من سطور M التالية على وصف للباب & ndash؛ عدد الغرف التي يؤدي منها والتي تؤدي إليها (يمكنك فقط السير من خلال الباب في اتجاه واحد) ، بالإضافة إلى عدد صحيح يضاف إلى مقدار المعرفة عند المرور من الباب (هذا الرقم لا يتجاوز 10000 في modulo). يمكن أن تؤدي الأبواب من غرفة إلى نفسها ، ويمكن أن يكون هناك أكثر من باب بين الغرفتين.
& nbsp؛
الإخراج:
عرض ":)" & - إذا كان بإمكانك الحصول على قدر غير محدود من المعرفة ، & quot؛: (& quot؛ & ndash؛ إذا تعذر تجاوز المتاهة ، وكان الحد الأقصى من المعرفة المكتسبة بخلاف ذلك.
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
2 2
1 2 3
1 2 7
|
7 |
نبسب ؛