판촉 행사

대형 슈퍼마켓 체인이 준비 중인 판촉 행사의 상금 비용을 계산하는 프로그램을 요청했습니다.

이 행사는 다음 규칙을 따릅니다.

• 참여를 원하는 고객은 자신이 결제한 영수증에 인적 사항을 적어 특별 추첨함에 넣습니다.
• 행사 기간 중 매일이 끝날 때, 추첨함에서 영수증 두 장을 꺼냅니다.
  • 먼저 금액이 가장 큰 영수증을 고르고,
  • 그다음 금액이 가장 작은 영수증을 고릅니다.
• 금액이 가장 큰 영수증을 낸 고객은 가장 큰 금액과 가장 작은 금액의 차이만큼 상금을 받습니다.
• 한 번의 구매로 여러 번 상을 받지 못하도록, 위 규칙으로 뽑힌 두 영수증은 추첨함에 되돌려 넣지 않습니다. 나머지 영수증은 모두 계속 행사에 남습니다.

거래량이 매우 많으므로, 매일이 끝나 금액이 가장 큰 영수증과 가장 작은 영수증을 꺼내기 직전에는 추첨함에 항상 영수증이 최소 두 장 있다고 가정할 수 있습니다.

행사 기간 동안 매일 추첨함에 넣은 영수증 금액이 주어질 때, 행사 전체에서 지급되는 상금의 총합을 계산하세요.

프로그램은 다음을 수행해야 합니다.

• 매일 추첨함에 넣은 영수증 금액 목록을 표준 입력에서 읽고,
• 연속된 날들에 지급된 상금의 총합을 계산하여,
• 그 결과를 표준 출력에 씁니다.

첫째 줄에 판촉 행사 기간(일수)을 나타내는 양의 정수 $n$ ($1 \le n \le 5000$)이 주어집니다.

이어지는 $n$개의 줄은 각각 하루를 나타냅니다. $(i+1)$번째 줄은 $i$번째 날 추첨함에 넣은 영수증 금액을 담고 있습니다. 줄은 그날의 영수증 개수 $k$ ($0 \le k \le 10^5$)로 시작하고, 이어서 영수증 금액을 나타내는 $k$개의 양의 정수가 옵니다. 각 금액은 $10^6$을 넘지 않습니다.

행사 전체 기간 동안 추첨함에 넣는 영수증의 총 개수는 $10^6$을 넘지 않습니다.

행사 전체 기간 동안 지급된 상금의 총합에 해당하는 정수 하나를 출력합니다.