Како што знаете, Здружението на информатичарите на Македонија треба да се акредитира за спроведување на државните натпревари по информатика. По добивање на акредитацијата, претседателот на ЗИМ планира да организира свечена вечера, на која ќе присуствуваат спонзори кои ќе донираат средства за организација на натпреварите, учество на меѓународни Олимпијади, планирање на летни школи и слично.

За анимирање на гостите на вечерата, ќе бидат задолжени Дојрана и Жарко. Поради долгогодишното искуство со барање средства за натпреварите, претседателот на ЗИМ однапред знае колку средства е спремен секој спонзор да донира. Дополнително, тој се јавил во ресторанот каде што ќе биде организирана свечената вечера, и се информирал кои спонзори ќе присуствуваат на истата, и на која позиција во ресторанот тие резервирале место. Сега, претседателот треба да направи поделба на ресторанот (кој има правоаголен облик), на начин што ќе повлече права линија помеѓу две точки кои се наоѓаат на границите од правоаголникот. Потоа, тој ќе ја задолжи Дојрана за дискусија со гостите кои се наоѓаат на едната страна на линијата во ресторанот, а Жарко за гостите кои се наоѓаат на другата страна.

Како да се повлече линијата е тешка задача, затоа што скоро сигурно Дојрана ќе даде предност на гостите од машки пол (и соодветно, сите од женски пол кои се на нејзината страна ќе се почувствуваат запоставено и ќе си отидат пред да донираат средства), додека Жарко ќе се концентрира на гостите од женски пол (и соодветно, сите од машки пол кои се на неговата страна од кафеаната ќе си отидат порано). Уште повеќе, тие двајца се и мрзеливи, па сите луѓе кои што ќе се најдат директно врз линијата со која претседателот ќе го подели ресторанот нема воопшто да бидат земени предвид од никој од двајцата, секој сметајќи дека тие се во ингеренција на другиот.

Ваша задача е да напишете програма која ќе пресмета колку најмногу средства може да добие Здружението, доколку претседателот го подели ресторанот на оптимален начин.

Влез

Во првата линија е запишан еден цел број N (2 <= N <= 1000), кој го означува бројот на гости - спонзори. Во секоја од следните N линии се запишани по три цели броеви Xi, Yi и Si (-100 000 <= Xi, Yi <= 100 000, и 1 <= Si <= 1000), кои ја означуваат локацијата (Xi, Yi) на секој од гостите, и средствата (Si) кои тој е спремен да ги донира. Во истата линија, покрај трите цели броеви Xi, Yi и Si, е запишан и еден знак ('M' или 'Z') кој го означува полот на гостинот.

Сите гости ќе бидат сместени на различна локација. Секогаш ќе постои најмалку еден гостин од машки пол, и најмалку еден гостин од женски пол.

Забелешка: Во тест случаи кои носат најмалку 30% од поените, ќе важи 2 <= N <= 50.

Излез

Отпечатете ја бараната вредност - колку најмногу средства може да добие здружението од донации.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
5
3 1 6 M
4 2 3 Z
5 3 6 M
5 1 3 Z
3 3 3 Z

излез
15

влез
4
1 1 5 M
1 3 3 M
1 2 4 Z
1 5 2 Z

излез
11

Објаснување за првиот пример: Видете ја сликата дадена во текстот на задачата. На неа, со квадратче се означени гостите од машки пол, додека со ѕвездичка се означени гостите од женски пол. Во заграда се запишани средствата кој е спремен секој од нив да ги донира.