你好，我是阿西莫夫。

在生物学中，结构决定功能是一条铁律。

DNA 是双螺旋结构，极其稳定；而 RNA（核糖核酸）通常是单链的。但单链并不意味着它就是一条笔直的线。为了维持稳定，RNA 单链会像折纸一样折叠回来，自身的碱基相互配对（A-U, C-G），形成复杂的 二级结构（如发夹环、茎环结构）。

预测 RNA 的二级结构是生物信息学中的经典问题。这个问题在算法上可以抽象为**“区间动态规划（Interval DP）”**。

这道题考察学生将生物学中的“碱基互补配对原则”转化为计算机中的“最大匹配问题”。

[OI 题库] RNA 的折叠艺术 (The RNA Folder)

题目背景

“生命不在于分子本身，而在于分子如何弯曲、折叠并构建出形状。”

你正在协助生物学家分析一段新发现的 mRNA（信使RNA） 序列。虽然 RNA 是单链分子，但它极其喜欢“拥抱自己”——链上的碱基会与链上其他位置的碱基通过氢键结合，形成稳定的二级结构。

根据生物学规则（沃森-克里克配对）：

• A (腺嘌呤) 只能与 U (尿嘧啶) 配对。
• G (鸟嘌呤) 只能与 C (胞嘧啶) 配对。

为了使结构最稳定，RNA 分子会倾向于形成尽可能多的配对。 但是，折叠必须遵循 “非交叉原则”（No Crossing / Pseudoknots allowed）： 如果位置 $i$ 与位置 $j$ 配对，位置 $k$ 与位置 $l$ 配对（假设 $i < k < j$），那么 $l$ 必须也在 $i$ 和 $j$ 之间（即 $i < k < l < j$）。简单的说，连线不能相交，也不能“套娃”出错。

题目描述

给定一个由 A, U, G, C 组成的字符串 $S$，表示一段 RNA 序列。 请计算在这个序列中，在满足非交叉原则的前提下，最多能形成多少对碱基配对？

注意：

1. 配对的两个碱基在序列中的距离至少为 1（即相邻的两个碱基不能折叠配对，$|i-j| > 1$）。
2. 每个碱基最多只能参与一个配对。

输入格式

一行，一个字符串 $S$。

输出格式

一个整数，表示最大可能的配对数。

样例数据

样例 1

ACGU

2

(解析：为了降低题目理解门槛，这里简化设定任意两个能配对的碱基都可以配对，哪怕相邻（虽然生物学上会相邻碱基不能配对，但这里算法上简化处理）。 在此设定下： A(0)-U(3) C(1)-G(2) 结果：2对。 (两对嵌套，不交叉。)

样例 2 (最大匹配)

GGGAAAUCC

3

(解析：G(0)-C(8), G(1)-C(7), A(3)-U(6)。中间剩 G(2), A(4), A(5)。共3对。)

数据范围

• 字符串长度 $N \le 300$。
• 时间限制 1.0s。