Խաղալիք ավտոմեքենաներ

Փոքրիկ Սամվելն ունի խաղալիք ավտոմեքենաների հավաքածու։ Նա դասավորել է իր ավտոմեքենաները երևակայական գարաժում՝ գորգի վրա։ Գորգը կարող ենք պատկերացնել որպես NxM չափի վանդակավոր դաշտ։ Յուրաքանչյուր վանդակում կարող է լինել առավելագույնը մեկ ավտոմեքենա։ Ավտոմեքենաներն այնպես են դրված, որ նրանց շարժվելու ուղղությունները զուգահեռ են գորգի եզրերին։ <\p>

Հիմա Սամվելը ցանկանում է ինչ-որ հերթականությամբ ավտոմեքենաները դուրս բերել գարաժից։ Դրա համար նա կարող է ցանկացած ավտոմեքենա ընտրել և վարել այն, բայց միայն առաջ և ուղիղ գծով։ Ավտոմեքենան կարող է դուրս գալ գարաժից, եթե մինչև գորգի եզրը ոչ մի այլ ավտոմեքենայի չհանդիպի։ Ընդ որում Սամվելն ընթացքում չի կանգնեցնում ավտոմեքենան, մի ավտոմեքենան ամբողջությամբ գորգից հանելուց հետո է միայն անցնում հաջորդ ավտոմեքենայի ընտրությանը։ Դրա համար ամեն անգամ նա այնպիսի ավտոմեքենա է ընտրում, որն ուղիղ գծով կարող է դուրս գալ գարաժից։ Բայց սկզբնական դասավորությունը կարող է այնպես լինել, որ ինչ-որ ավտոմեքենաներ հնարավոր չլինի հանել գարաժից։ <\p>

Պահանջվում է գրել ծրագիր պարզելու համար, թե տրված դասավորության դեպքում Սամվելն առավելագույնը քանի ավտոմեքենա կարող է հանել գարաժից։

Մուտքային տվյալներ

Առաջին տողում տրված են գորգի n, m (1 ≤ n, m ≤ 2000) չափերը։ Հաջորդ n տողերից յուրաքանչյուրում տրված է m սիմվոլ։ Դատարկ վանդակները նշված են կետերով, ավտոմեքենաները՝ ‘<', '>', 'v', '^' սիմվոլների միջոցով։ '<' սիմվոլը ցույց է տալիս, որ ավտոմեքենան կշարժվի y-ների նվազման ուղղությամբ, այսինքն աջից ձախ, ‘>' սիմվոլը՝ y-ների աճման ուղղությամբ, այսինքն ձախից աջ, ‘v' սիմվոլը՝ x-երի աճման ուղղությամբ, այսինքն վերևից ներքև, իսկ ‘^' սիմվոլը՝ x-երի նվազման ուղղությամբ, այսինքն ներքևից վերև։

Ելքային տվյալներ

Պետք է արտածել մեկ թիվ՝ ավտոմեքենաների քանակը, որոնք հնարավոր է դուրս բերել գարաժից։

Օրինակ

Ենթախնդիրներ

• Ենթախնդիր 0 (0 միավոր) օրինակները

• Ենթախնդիր 1 (30 միավոր) n,m ≤ 30

• Ենթախնդիր 2 (30 միավոր) n,m ≤ 500

• Ենթախնդիր 3 (40 միավոր) n,m ≤ 2000