旅行推銷員問題是一個經典問題，給定 $N$ 座城市，我們從一座城市出發，經過所有其它城市恰好一次，最後再返回起點城市；在所有的路線中，我們想要找到行走總距離最短的路線。大明最近在研究如何求解旅行推銷員問題，有朋友跟他提出一個推測，一條候選路線和最佳路線的結構越相似，則該候選路線的總距離會越短。

　　大明對這個推測很感興趣，他想了一個分析的手法如下：

• 首先，他定義兩條路線的結構相似度為最長共同子序列的長度。令 $X_i$ 和 $X_j$ 代表兩條路線，$Xi=[𝑥_{𝑖,1},𝑥_{𝑖,2},\dots ,𝑥_{𝑖,𝑁}]$，$Xj=[𝑥_{j,1},𝑥_{j,2},\dots ,𝑥_{j,𝑁}]$。
  若有一個 $X_i$ 和 $X_j$ 的共同子序列 $C$ 長度為 $K$，則 $C$ 可表示為 $C=[𝑥_{𝑖,𝑝_1},𝑥_{𝑖,𝑝_2},\dots ,𝑥_{𝑖,𝑝_𝐾}]=[𝑥_{j,𝑞_1},𝑥_{j,𝑞_2},\dots ,𝑥_{j,𝑞_𝐾}]$，其中 $1\le 𝑝_1<𝑝_2<\dots <𝑝_𝐾\le N$ 而且 $1\le 𝑞_1<𝑞_2<\dots <𝑞_𝐾\le N$。
  下面的圖例分別代表兩種路線 $[1,2,3,4,5,6,7,1]$ 和 $[1,3,4,5,2,6,7,1]$，它們的最長共同子序列為 $[1,3,4,5,6,7,1]$，長度為 $7$。
  
• 接著，給定 $M$ 條路線 $X_1$, $X_2$, $\dots$, $X_M$，令 $d(X_i)$ 代表路線 $X_i$ 的行走總距離，$l(X^*, X_i)$ 代表最短路線 $X^*$ 和路線 $X_i$ 的結構相似度，他想找到解集合 $S=\{𝑋_{𝑠_1},𝑋_{𝑠_2},\dots ,𝑋_{𝑠_𝑅}\}$，其中 $1\le s_i\le M$，$1\le i\le R$，滿足「相似度遞增、行走總距離遞減」的性質：
  $l(X^*, 𝑋_{𝑠_𝑖})<l(X^*, 𝑋_{𝑠_{𝑖+1}})$ 而且 $d(𝑋_{𝑠_𝑖})>d(𝑋_{𝑠_{𝑖+1}})$，$1\le i\le R-1$。

　　舉例來說，給定 $N=7$ 座城市，城市 $1$ 為路線起點和終點。我們有六條路線，其中第一條路線為最短路線。

　　此例中，{$X_6$, $X_4$, $X_1$} 是一個滿足性質的集合：$(4,210)\rightarrow (7,120)\rightarrow (8,100)$，其集合大小為 $3$。{$X_6$, $X_3$, $X_4$, $X_1$} 也滿足性質：$(4,210)\rightarrow (6,150)\rightarrow (7,120)\rightarrow (8,100)$，其大小為 $4$。本例中能找到滿足性質的最大集合，其大小為 $4$。

　　大明認為這個 $S$ 內的解的個數越多，就越支持朋友的推測。請你撰寫一個程式，給定數個路線，計算從中能找到的最大 $S$ 的解個數。