신발장
시간 제한2초메모리 제한1024 MB
선반 높이와 신발 크기 조건을 동시에 만족하는 키가 없는 신발 쌍의 개수를 구합니다.
문제
메이블의 가족에게 새 신발장이 생겼다. 가족이 많고 손님도 많아서 신발장은 금방 가득 찼다. 메이블은 사람들이 신발장에 신발을 넣고 꺼내는 모습을 주의 깊게 지켜봤다.
이 신발장은 특이하게도 선반마다 높이가 다르다. 첫 번째 선반은 바닥에서 높이에 있고, 두 번째 선반은 높이에 있다. 이런 식으로 번째 선반은 높이에 있다. 사람들이 신발을 놓고 꺼내는 방식을 살핀 메이블은 다음을 알아냈다. 키가 인 사람은 높이가 보다 큰 선반에는 신발 한 켤레를 놓을 수 없고, 높이가 보다 작은 선반에도 놓을 수 없다. 또 키가 인 사람의 발 크기는 적어도 이상이고, 많아야 이하이다.
메이블은 신발장을 보고 일부 신발이 마법처럼 나타난 것 같다고 느낀다. 그녀가 관찰한 내용으로 보면, 누구도 그 신발을 거기에 놓을 수 없었다. 관찰 내용에 맞지 않는 신발 켤레의 수를 세어서 그녀의 확인을 도와라.
입력
첫 줄에 신발장의 선반 수 이 주어진다 ().
둘째 줄에 메이블이 도출한 계수 , , 가 주어진다 (; ).
다음 개의 줄에 선반이 설명된다. 번째 선반의 설명은 선반 높이 로 시작한다 (, 모든 에 대해 ). 이어서 그 선반에 놓인 신발 켤레 수 가 주어진다 (). 그 뒤에 그 선반의 신발 크기 가 개 주어진다 ().
모든 의 합은 을 넘지 않는다.
출력
메이블의 관찰에 맞지 않는 신발 켤레의 수를 한 줄에 출력한다.
힌트
주어진 테스트에는 메이블의 관찰에 맞지 않는 신발 켤레가 정확히 두 개 있다. 높이 2인 선반에 있는 크기 1의 켤레와, 높이 4인 선반에 있는 크기 3의 켤레이다.