قرر أحد الفرق المشاركة في الأولمبياد العودة إلى الوطن بالقطار. في الوقت نفسه ، يريد الرجال العودة إلى المنزل في أسرع وقت ممكن. لسوء الحظ ، لا تذهب جميع القطارات الكهربائية من المدينة التي تقام فيها الأولمبياد إلى المحطة التي يعيش فيها الرجال. والأكثر هجومًا هو أنه لا تتوقف عنده جميع القطارات الكهربائية التي تمر عبر محطتها (وكذلك بشكل عام ، لا تتوقف القطارات الكهربائية في جميع المحطات التي تمر بها).
& nbsp؛
جميع المحطات الموجودة على الخط مرقمة من 1 إلى N. وفي الوقت نفسه ، تقع المحطة رقم 1 في المدينة التي يقام فيها الأولمبياد ، وفي الوقت الذي يصل فيه الرجال إلى المحطة 0. المحطة التي يجب على اللاعبين الوصول إليها تحتوي على الرقم E.
& nbsp؛
اكتب برنامجًا يحسب ، وفقًا لجدول القطار ، الحد الأدنى من الوقت الذي يمكن أن يكون فيه الرجال في المنزل.
& nbsp؛
إدخال
في ملف الإدخال & nbsp؛ الأرقام N (2 & le؛ N & le؛ 100) و E (2 & le؛ E & le؛ N) مكتوبة أولاً. ثم يتم كتابة الرقم M (0 & le؛ M & le؛ 100) ، مشيرًا إلى عدد مرات تشغيل القطارات. فيما يلي وصف لرحلات M للقطارات الكهربائية. يبدأ وصف كل رحلة قطار بالرقم Ki (2 & le؛ Ki & le؛ N) & mdash؛ عدد المحطات التي يتوقف عندها ، متبوعًا بـ Ki أزواج من الأرقام ، الرقم الأول من كل زوج يحدد رقم المحطة ، والثاني & mdash ؛ الوقت الذي يتوقف فيه القطار في هذه المحطة (يتم التعبير عن الوقت بعدد صحيح من 0 إلى 10
9 ). يتم ترتيب المحطات داخل نفس الرحلة بترتيب زمني تصاعديًا. خلال رحلة واحدة ، يتحرك القطار في نفس الاتجاه طوال الوقت و [مدش] ؛ إما بعيداً عن المدينة أو باتجاه المدينة.
& nbsp؛
الإخراج
لإخراج الملف & nbsp؛ طباعة رقم واحد و [مدش] ؛ الحد الأدنى من الوقت الذي يمكن أن يكون فيه الرجال في محطتهم. إذا لم يتمكنوا من الوصول إلى هناك عن طريق خطوط القطار الحالية ، اطبع & ndash؛ 1.
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
5 2
2
4 1 1 3 2 4 10 5 20
3 5 10 4 15 2 40
|
40 |