문제

넙죽이는 매년 ‘별빛 축제’의 DJ로 무대에 선다. 올해 그는 같은 장르별 대표곡만 모아, 에너지 상승폭을 최대화하는 최적의 플레이리스트를 찾아야 한다. 장르가 섞이거나 즐거움이 떨어지면 관객이 떠나기에, 넙죽이는 순서를 신중히 골라야된다.

축제에서 틀 음악 리스트로 개의 곡이 준비되어 있고, 이 곡들은 총 개의 장르 안에 속해 있다.
각 곡마다 장르와 곡에 대한 점수(, 는 양수) 가 주어진다.

관객은 연속해서 재생되는 번째 곡과 번째 곡의 점수 차이 만큼의 즐거움을 얻는데, 이는 를 의미하며, 이 값이 클수록 더 큰 즐거움을 느낀다. 단, 다음 상황이 발생하면 축제를 즐기던 사람들은 모두 나가버린다.

1. 장르 혼합
   연속 재생되는 두 곡의 장르가 다른 상태가 2번이상 등장한 경우

넙죽이는 모든 곡을 즐길 수 있을 때의 최대 총 즐거움 을 구하고자 한다.

입력

첫 번째 줄에 정수 ()과 정수 () 이 입력으로 주어진다.

두 번째 줄부터 번째 줄까지 (), () 가 주어지며, 이는 곡 가 장르와 점수를 가지고 있음을 의미한다.

출력

개의 줄에 축제가 무사히 마무리 될때의 최대 총 즐거움 을 출력한다.