სუპერბალანსი

დროის ლიმიტი: 2 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

შემავალი მონაცემები: cin

გამომავალი მონაცემები: cout


ბესის, როგორც იცით, მოსწონს გახსნილი და დახურული ფრჩხილებისაგან შედგენილი დაბალანსებული სტრიქონები. მას განსაკუთრებით მოსწონს .. "სუპერდაბალანსებული" სტრიქონები, რომლებიც იწყება გარკვეული რაოდენობის გახსნილი ფრჩხილებით და მთავრდება იგივე რაოდენობის დახურული ფრჩხილებით. მაგალითად ასეთი:

(((())))

ერთ დღეს, ბოსლის მიდამოებში სეირნობისას ბესიმ აღმოაჩინა, რომ ძროხების ნაკვალევი წარმოადგენს N x N ზომის მატრიცას, რომლის თითოეული ელემენტი არის გახსნილი ან დახურული ფრჩხილი. ბესის უნდა, რომ დაიწყოს მატრიცის ზემოთა მარცხენა წერტილიდან და იმოძრაოს ისეთი ტრაექტორიით, რომ მიიღოს მაქსიმალური სიგრძის "სუპერდაბალანსებული" სტრიქონი, ანუ, ჯერ გახსნილი ფრჩხილები, შემდეგ კი იგივე რაოდენობის დახურული ფრჩხილები. დაეხმარეთ მას მაქსიმალური "სუპერდაბალანსებული" სტრიქონის სიგრძის გამოთვლაში.

ყოველ ნაბიჯზე ბესის შეუძლია გადაადგილება ზემოთ, ქვემოთ, მარჯვნივ ან მარცხნივ, თანაც ისე, რომ ერთ ადგილზე ორჯერ არ უნდა მოხვდეს. არ არის გამორიცხული, რომ გარკვეული მატრიცების შემთხვევაში "სუპერდაბალანსებული" სტრიქონი საერთოდაც არ მიიღებოდეს.

 

შეტანის ფორმატი:

* სტრიქონი 1: ერთი მთელი რიცხვი N (2 <= N <= 5).

* სტრიქონები 2..N+1: თითოეული სტრიქონი შეიცავს N სიგრძის სტრიქონს, რომელიცედგება გახსნილი და დახურული ფრჩხილებისაგან. ამგვარად მიიღება N x N ზომის მატრიცა, რომლის ელემენტებია გახსნილი და დახურული ფრჩხილები.

 

გამოტანის ფორმატი:

* სტრიქონი 1: მაქსიმალური "სუპერდაბალანსებული" სტრიქონის სიგრძე. თუ ასეთი სტრიქონი არ შედგება (მაგალითად, თუ ზედა მარცხენა სიმბოლო დახურული ფრჩხილია), გამოტანილი უნდა იქნეს 0.




მაგალითები

შესატანი მონაცემები
4 (()) ()(( (()( )))) დაკოპირება
გამოსატანი მონაცემები
8 დაკოპირება

შენიშვნა

იმ ნაბიჯების მიმდევრობა, რომლიაც მიიღება 8 სიგრძის მქონე სტრიქონი, ასეთია:

1())

2)((

345(

876)