{"problem":{"name":"Souvenir","description":{"content":"There are $N$ cities. There are also one-way direct flights that connect different cities.   The availability of direct flights is represented by $N$ strings $S_1,S_2,\\ldots,S_N$ of length $N$ each. I","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc286_e"},"statements":[{"statement_type":"Markdown","content":"There are $N$ cities. There are also one-way direct flights that connect different cities.  \nThe availability of direct flights is represented by $N$ strings $S_1,S_2,\\ldots,S_N$ of length $N$ each. If the $j$\\-th character of $S_i$ is `Y`, there is a direct flight from city $i$ to city $j$; if it is `N`, there is not.  \nEach city sells a souvenir; city $i$ sells a souvenir of value $A_i$.\nConsider the following problem:\n\n> Takahashi is currently at city $S$ and wants to get to city $T$ (that is different from city $S$) using some direct flights.  \n> Every time he visits a city (including $S$ and $T$), he buys a souvenir there.  \n> If there are multiple routes from city $S$ to city $T$, Takahashi decides the route as follows:\n> \n> *   He tries to minimize the number of direct flights in the route from city $S$ to city $T$.\n> *   Then he tries to maximize the total value of the souvenirs he buys.\n> \n> Determine if he can travel from city $S$ to city $T$ using the direct flights. If he can, find the \"number of direct flights\" and \"total value of souvenirs\" in the route that satisfies the conditions above.\n\nYou are given $Q$ pairs $(U_i,V_i)$ of distinct cities.  \nFor each $1\\leq i\\leq Q$, print the answer to the problem above when $S=U_i$ and $T=V_i$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 300$\n*   $1\\leq A_i\\leq 10^9$\n*   $S_i$ is a string of length $N$ consisting of `Y` and `N`.\n*   The $i$\\-th character of $S_i$ is `N`.\n*   $1\\leq Q\\leq N(N-1)$\n*   $1\\leq U_i,V_i\\leq N$\n*   $U_i\\neq V_i$\n*   If $i \\neq j$, then $(U_i,V_i)\\neq (U_j,V_J)$.\n*   $N,A_i,Q,U_i$, and $V_i$ are all integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\ldots$ $A_N$\n$S_1$\n$S_2$\n$\\vdots$\n$S_N$\n$Q$\n$U_1$ $V_1$\n$U_2$ $V_2$\n$\\vdots$\n$U_Q$ $V_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc286_e","tags":[],"sample_group":[["5\n30 50 70 20 60\nNYYNN\nNNYNN\nNNNYY\nYNNNN\nYNNNN\n3\n1 3\n3 1\n4 5","1 100\n2 160\n3 180\n\nFor $(S,T)=(U_1,V_1)=(1,3)$, there is a direct flight from city $1$ to city $3$, so the minimum possible number of direct flights is $1$, which is achieved when he uses that direct flight. In this case, the total value of the souvenirs is $A_1+A_3=30+70=100$.\nFor $(S,T)=(U_2,V_2)=(3,1)$, the minimum possible number of direct flights is $2$. The following two routes achieve the minimum: cities $3\\to 4\\to 1$, and cities $3\\to 5\\to 1$. Since the total value of souvenirs in the two routes are $70+20+30=120$ and $70+60+30=160$, respectively, so he chooses the latter route, and the total value of the souvenirs is $160$.\nFor $(S,T)=(U_3,V_3)=(4,5)$, the number of direct flights is minimum when he travels cities $4\\to 1\\to 3\\to 5$, where the total value of the souvenirs is $20+30+70+60=180$."],["2\n100 100\nNN\nNN\n1\n1 2","Impossible\n\nThere may be no direct flight at all."]],"created_at":"2026-03-03 11:01:14"}}