همانطور که می‌دانید ماشین زمان اختراع شده و حتی آقابزرگ هم برای آزمایش از آن استفاده کرده است. هدف او رفتن به سال 1500 بوده ولی ظاهرا ماشین مشکلاتی داشته و او به زمانی دیگر رفته است. محققان اثبات کرده اند که از ابتدا تا نابودی سیاره‌ی زمین را می‌توان با استفاده از خاصیت «کیتی» `n` نقطه بحرانی از زمین به `k` عصر مختلف تقسیم کرد که باشماره‌های 1 تا `k` شماره‌گذاری شده‌اند. به طور دقیق‌ر به هر عصر یه رشته‌ی `n` بیتی اختصاص داده شده به طوری که اگر نقطه‌ی `i`ام در آن عصر خاصیت «کیتی» داشته باشد، بیت `i`ام آن یک است و در غیر این صورت برابر با صفر است(دانستن خاصیت یتی تأثیری بر حل سوال نخواهد داشت). رشته‌ی مربوط به هیچ دو عصری یکسان نیست. آقا بزرگ می‌خواهد در سریع‌تری زمان ممکن بفهمد در کدام عصر قرار دارد. برای این کار او می‌تواند یکی از نقاط بحرانی زمنی را انتخاب کند و در آن قرار بگیرد. سپس می‌تواند برای انتقال بین نقاط بحرانی از جاده‌های باستانی زمین استفاده کند. این جاده ها دو طرفه هستند و بین `n` نقطه‌ی بحرانی ساخته شده‌اند و آقابزرگ می دند که برای عبور از هریک از جاده‌ها چقدر زمان نیاز دارد. آقابزرگ، در ره نقطه‌ی بحرانی می‌تواند خاصیت «کیتی» آن نقطه را بررسی کند. او بسیار باهوش است و در نتیجه در اولین لحظه‌ای که بتواند با توجه به خواص کیتی نقاط بحرانی عصر فعلی را تشخیص دهد، متوقف می‌شود و بلافاصله به سال 1500 می رود. آقا بزرگ بسیار عجله دارد و می‌خواهد هرچه سریع‌تر به سال 1500 برود. به همین دلیل، می‌خواهدبدانه مستقل از عسری که در آن است، حداکثر چقدر زمان لازم دارد تا بتواند به سال 1500 برود؟ ## ورودی سطر اول ورودی شامل سه عدد طبیعی `k` تعداد عصرهای مختلف زمین، `n` تعداد نقاط بحرانی، `m` تعداد جاده‌های باستانی است. در سطر `i`ام از `k` سطر بعدی، رشته‌ی `n` بیتی متناظر با عصر `i`ام آمده است. در هر یک از `m` سطر بعدی، عدد `w, v ,u` آمده است که وجود یک جاده‌ی باستانی بین دو نقطه‌ی بحرانی `u` و `v` است به طوری که طی کردن آن توسط آقابزرگ، `w` ثانیه طول می کشد. ## خروجی در تنها سطر خروجی، پاسخ مسئله را چاپ کنید. ## محدودیت‌ها + $1 \leq n,m \leq 1000$ + $ 1 \leq k \leq 11$ + $ 1 \leq w \leq 10^5 , u \ne v , 1 \leq u,v \leq n$ ## مثال ورودی نمونه ۱ ``` 5 4 6 0001 0000 0010 0100 1000 1 2 1 2 3 1 3 4 1 1 4 10 1 3 10 2 4 10 ``` خروجی نمونه ۱ ``` 3 ``` ورودی نمونه ۲ ``` 3 3 3 000 001 011 1 2 1 1 3 1 2 3 3 ``` خروجی نمونه ۲ ``` 2 ``` ۲۶امین دوره المپیاد کامپیوتر - آزمون اول - ۱۳۹۴/۵/۳۱