B - 天下一魔力発電

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400

問題文

天下一魔力発電所は不思議な魔術で電気を生み出すことができる発電所です。

魔力発電に用いる燃料は以下の様な文字列 S です。

S() で構成されており、S の文字数は偶数です。

天下一ワープロでこの文字列を対応の取れた文字列に書き換えることで魔力発電に成功します。

対応が取れた文字列とは、以下の文字列です。

  • () は対応が取れた文字列である。
  • T が対応が取れた文字列であるとき、(T) も対応が取れた文字列である。
  • T, U が対応が取れた文字列であるとき、TUも対応が取れた文字列である。

天下一ワープロには以下 4 通りの操作があります。

はじめはカーソルは S の先頭の文字を指します。

  1. カーソルを右に動かす(カーソルが末尾の文字を指す場合は動かない)
  2. カーソルを左に動かす(カーソルが先頭の文字を指す場合は動かない)
  3. カーソルが指す文字が ( のとき、その文字を ) に変更する
  4. カーソルが指す文字が ) のとき、その文字を ( に変更する

たとえば S が次の文字列の場合、

())(()))

1, 4 と操作を行うことで

(()(()))

という対応が取れた文字列にすることができます。

発電所の責任者であるフデくんは最も少ない操作回数で文字列を対応が取れた文字列に書き換えたいです。

S が与えられるので、対応の取れた文字列に書き換える最も少ない操作回数を求めてください。

制約

  • S の文字数 |S| は偶数
  • 2 \leq |S| \leq 100

入力

入力は以下の形式で標準入力から与えられる。

S

出力

対応の取れた文字列に書き換える最も少ない操作回数を出力せよ。出力の末尾に改行を入れること。


入力例 1

())(()))

出力例 1

2

問題文中に登場したケースです。


入力例 2

((((

出力例 2

5

1, 1, 3, 1, 3 と操作することで対応のとれた文字列になります。


入力例 3

)))(((

出力例 3

9