Description

小欣在公园玩时发现有个玩小游戏的地方，小游戏的规则是：有两排标有字符的球，字符属于{A，T，C，G}，第1排有N1个球，第2排有N2个球（1<=N1,N2<=50000)，在第1排的球中选出1些来和第2排的配对，每配出1对就得1分，已经配对了的就不能再用了。小欣觉得这个游戏太简单了，不就是用个…就可以了吗？但他发现规则的最后1行说：配对的连线不能相交，相交的概念就是对于第1排的I，J这2个球，它们配对的分别是F[I]，F[J]，它们相交当且仅当I<J and F[I]>F[J]。这就难倒小欣了，现在请你帮助小欣编程求出最大得分。

Input

Output

2 2

CT

AG

Sample Input

Sample Output

Hint

Source