Moving Mountains

The islands of Polylogonia and Quasilogonia have mountain ranges whose profiles are made of slopes at $45^\circ$. A profile is described from left to right by a string of “U” (uphill) and “D” (downhill) characters. The two profiles have the same length. Each mountain range starts and ends at sea level and never goes below it. Since it starts and ends at sea level, each profile has the same number of “U” and “D” characters. The figure below shows the profile “UUDUUDUDDD”.

The Island Contour Planning Company (ICPC) owns a machine that is capable of filling valleys in a very specific way. In one operation, it chooses an island and covers an entire uphill slope with earth. This slope runs from the bottom of a valley to the first peak to its right. More precisely, the operation replaces a substring of that island’s profile of the form “$\texttt{DU}~^k~\texttt{D}$” ($k \geq 1$) with “$\texttt{U}~^k~\texttt{DD}$”, where “$\texttt{U}~^k$” denotes $k$ consecutive “U” characters. All other characters remain unchanged. The machine cannot remove earth, only add it in the way just described.

The figure below shows one operation of the machine: the part “$\texttt{DU}~^2~\texttt{D}$” marked by the brace on the left becomes “$\texttt{U}~^2~\texttt{DD}$” on the right, where the hatched strip is the earth that was added.

The ICPC wants to make the two profiles identical using its machine. It can be shown that this is always possible. Find the minimum total number of operations needed.

Input

The first line contains a string $P$ ($2 \leq |P| \leq 2 \times 10^{5}$), representing the profile of Polylogonia.

The second line contains a string $Q$ ($|Q| = |P|$), representing the profile of Quasilogonia.

Each string is made of the uppercase letters “U” and “D”, indicating respectively uphill and downhill sections of the corresponding mountain range. In each string the number of “U” and “D” characters is the same, and no prefix has more “D” characters than “U” characters.

Output

Output a single line with an integer indicating the minimum total number of operations needed to transform the profiles $P$ and $Q$ into the same profile.

UUDDUD
UUUDDD

2

UUDDUUUDUUDDDD
UUDUUDDUUUDDDD

4

UDUUDUUUDDDD
UDUUUDDUUDDD

3