Problem
एरिक विश्वविद्यालय में एक सुरक्षा गार्ड के रूप में काम करता है, इसलिए दिन भर के काम के बाद वह इमारत के चारों ओर घूमता है और रात में रोशनी बंद कर देता है।
इमारत में n मंजिलें हैं और बाईं और दाईं ओर दो सीढ़ियाँ हैं। गलियारे के साथ-साथ प्रत्येक मंजिल पर मी कमरे हैं जो बाएँ और दाएँ सीढ़ियों को जोड़ते हैं। दूसरे शब्दों में, भवन को n पंक्तियों और m + 2 स्तंभों के साथ एक आयत के रूप में दर्शाया जा सकता है, जहाँ पहला और अंतिम स्तंभ — सीढ़ियाँ, और मध्य में m स्तंभ — कमरे।
एरिक अब बाईं सीढ़ियों पर पहली मंजिल पर खड़ा है। वह हर जगह लाइट बंद करना चाहता है, जबकि वह मौजूदा फ्लोर की सभी लाइटें बंद करने से पहले ऊपर की मंजिल तक नहीं जाना चाहता। बेशक, लाइट बंद करने के लिए एरिक को कमरे में होना चाहिए। एरिक सीढ़ियों से एक मंजिल तक चलने या अगले कमरे में जाने / अगले कमरे से सीढ़ियों या उसी मंजिल पर सीढ़ियों तक जाने में एक मिनट बिताता है। एरिक जिस कमरे में है उसकी लाइट बंद करने में उसका समय नहीं लगता है।
बिल्डिंग की सभी लाइटें बंद करने के लिए कम से कम समय निकालने में एरिक की मदद करें।
ध्यान दें कि एरिक को अपनी मूल स्थिति में लौटने की ज़रूरत नहीं है, और यह भी कि उसे उन कमरों में जाने की ज़रूरत नहीं है जहाँ रोशनी पहले से ही बंद है।
इनपुट:
पहली पंक्ति में दो पूर्णांक हैं n और m (1 ≤ n ≤ 15, 1 ≤ m ≤ m ≤ 100) — क्रमशः मंजिलों की संख्या और प्रत्येक मंजिल पर कमरों की संख्या।
अगली n पंक्तियों में भवन का विवरण है। प्रत्येक पंक्ति में शून्य की एक स्ट्रिंग होती है और लंबाई m + 2 होती है जो एक मंजिल का वर्णन करती है (बाएं सीढ़ियां, फिर m कमरे, फिर दाएं सीढ़ियां), जहां 0 का अर्थ है रोशनी बंद है और 1 का अर्थ है रोशनी चालू है। फर्श ऊपर से नीचे के क्रम में दिए गए हैं, विशेष रूप से, अंतिम पंक्ति पहली मंजिल का वर्णन करती है।
प्रत्येक पंक्ति के पहले और अंतिम अक्षर सीढ़ियों का वर्णन करते हैं, इसलिए वे हमेशा 0 होते हैं।
आउटपुट:
एक नंबर प्रिंट करें — सभी लाइटों को बंद करने के लिए आवश्यक न्यूनतम संभव समय।
उदाहरण:
<तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स;">
<शरीर>
| इनपुट |
आउटपुट |
2 2
0010
0100 |
5 |
3 4
001000
000010
000010 |
12 |
स्पष्टीकरण:
पहले उदाहरण में, एरिक पहले 1 पहली मंजिल पर कमरे में जाएगा, और फिर — किसी भी सीढ़ी का उपयोग करके दूसरी मंजिल पर 2 कमरे के लिए।
दूसरे उदाहरण में, वह सबसे पहले पहली मंजिल पर चौथे कमरे में जाएगा, दाहिनी सीढ़ियों से एक मंजिल ऊपर जाएगा, दूसरी मंजिल पर चौथे कमरे में प्रवेश करेगा, फिर से दाईं सीढ़ियों से ऊपर जाएगा, दूसरे पर जाएगा आखिरी मंजिल पर कमरा।