User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

50.0% (6/12)

Description

(故事純屬虛構,如有雷同純屬巧合)

今天你想要從成功大學店畢業,需要進行口試,只有通過口試你才能夠從成功大學店畢業!

你孤孤單單地站在講台上,台下有三排教授坐著看著你,每排有 $N$ 個座位:

  • 沒有坐人的地方使用 ? 表示
  • 每個教授只專精一個領域 (使用大寫字母代表教授的領域)
  • 同樣專精領域的教授會才可以互相討論組成討論團

這裡的教授比較特別,喜歡前後排討論,每個討論團中會有三個教授,且剛好都在不同排,又因為不想受到干擾,所以任兩個討論團的教授座位不得交叉,也就是其中一個討論團的全部教授座位編號都比另一團同一排的教授座位編號小。

舉例來說:

???ABC???
????ABC??
?BABC????

  • 如果兩個討論團的教授座位分別為 ${4, 5, 3}$ 與 ${5, 6, 4}$,這樣就是合法的討論團,因為 $4<5, 5<6, 3 < 4$。
  • 如果兩個討論團的教授座位分別為 ${4, 5, 3}$ 與 ${5, 6, 2}$,這樣就是不合法的討論團,因為 $4<5, 5<6$ 卻 $3>2$ 。

只有討論團的教授會對你展現鋒利的眼神,沒有在討論團的教授會選擇 Love and Peace(一種慈悲為懷的)眼神,請問你最多受到多少教授鋒利的眼神。

Input Format

第一行會有一個整數 $N, 1\leq N \leq 300$,代表每排的座位。
第二行開始到第四行,每行會有 $N$ 個字元,字元只可能為大寫字母或是 ?
若為大寫字母,則代表那個座位教授的專精領域代號。
若為 ?,則代表那個座位為空。

Output Format

只會有一行,一個整數,代表你最多受到多少教授鋒利的眼神

Sample Input 1

12
AAAABBBBCEFG
A??AB?BE?FCG
A?AB?BC?????

Sample Output 1

15

Sample Input 2

30
?A???D?DCDDCB?D?CDDD?BDC?B?D?B
DCDC?ADAC?ACCD?BD?CD?BA??D?DD?
DD?A?CBBDBCDCAB??CC?DD?BCCAA?C

Sample Output 2

30

Hints

對於第一筆測試資料來說,其中一種可能的討論團分佈,如下

共五組15人。

記憶體使用過大有可能顯示 RE 與 MLE,請各位注意自己的記憶體使用量。

Problem Source

Subtasks

No. Testdata Range Score
1 0~15 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1500 65536 65536 1
1 1500 65536 65536 1
2 1500 65536 65536 1
3 1500 65536 65536 1
4 1500 65536 65536 1
5 1500 65536 65536 1
6 1500 65536 65536 1
7 1500 65536 65536 1
8 1500 65536 65536 1
9 1500 65536 65536 1
10 1500 65536 65536 1
11 1500 65536 65536 1
12 1500 65536 65536 1
13 1500 65536 65536 1
14 1500 65536 65536 1
15 1500 65536 65536 1