Tag Discussion Solution Statistics Submit
 

RUPC 2013 (OUPC)
 

Parentheses

Time Limit : 1 sec, Memory Limit : 65536 KB

()

Problem Statement

文字列Sがある.はじめ,Sは空文字列である.
以下の処理をn個順番に行う.

  • Sの末尾にp_i(="("または")")をx_i個追加する.

処理を施した後,Sがバランスのとれた文字列であるかどうか判定せよ.

「文字列のバランスが取れている」とは,次のように定義される.

  • 空文字列はバランスが取れている.
  • バランスの取れている文字列abに対して,a + b(+は文字列の連結を表す)はバランスが取れている.
  • バランスの取れている文字列aに対して,"(" + a + ")"はバランスが取れている.

Input

入力は以下の形式に従う.与えられる数は全て整数である.

n
p_1 x_1
. . .
p_n x_n

Constraints

  • 1≦n≦1,000
  • 1≦x_i≦10^6
  • p_iは"("または")"

Output

バランスがとれているときは"YES"を,そうでなければ"NO"を1行に出力せよ.

Sample Input 1

3
( 5
) 4
) 1

Output for the Sample Input 1

YES

文字列S="((((()))))"はバランスがとれている.

Sample Input 2

5
( 2
) 2
( 3
) 1
) 2

Output for the Sample Input 2

YES

Sample Input 3

2
) 1
( 1

Output for the Sample Input 3

NO

Source: Ritsumeikan University Competitive Programming Camp 2013, Day2 , Problem set from Osaka University teams, Shiga, Japan, 2013-03-12
Problem Setter:  komiya