در یک جامعه‌ی متمدن مردم برای اداره‌ی امور مملکت رئیس‌جمهور منتخب خود را برمی‌گزینند. کرومزوم بیست‌و سوم هر انسانی در این جامعه نشان‌دهنده‌ی علایق سیاسی وی می‌باشد و حاوی یک رشته از حروف $a$ تا $z$ می‌باشد. پس از انتخاب رئیس‌جمهور هر کسی به اندازه‌ی شباهت علایق سیاسی خود با وی خوشحال می‌شود و هدف در این جامعه‌ی پیشرفته بیشینه کردن میزان خوش‌حالی افراد است. شباهت علایق سیاسی دو نفر برابر طول بزرگ‌ترین پیشوند کرومزوم ۲۳ آن دو می‌باشد. با داشتن اطلاعات کرومزومی افراد جامعه باید رشته‌ای ارائه کنید که در صورت رئیس‌جمهور شدن فردی با این رشته‌ی کرومزومی مجموع میزان خوش‌حالی افراد بیشینه شود. در این صورت مهندسین ژنتیک، می‌توانند چنین فردی را بسازند تا سکان هدایت جامعه را در دست گیرد.

در سطر اول، ابتدا $n$‌تعداد افراد مورد بررسی از جامعه و سپس $m$ طول کرومزوم ۲۳ یک فرد جامعه است. در هر یک از $n$‌سطر بعدی رشته‌ی کرومزمی یک فرد می‌آید.($1\leq n \leq 10^4$ و $1 \leq m \leq 10^3$)

در سطر اول میزان خوش‌حالی افراد را بنویسید و در سطر بعد رشته‌ی کرومزمی رئیس‌جمهور منتخب را بنویسید. لزومی ندارد که رئیس‌جمهور از جامعه‌ی نمونه انتخاب شود!!

• محدودیت زمان: ۱۰ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل