만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

신발장

시간 제한2초메모리 제한1024 MB

요약
선반 높이와 신발 크기 조건을 동시에 만족하는 키가 없는 신발 쌍의 개수를 구합니다.
난이도

쉬움10점 중 3점

유형
수학, 구현
정답자
아직 제출이 없습니다

문제

메이블의 가족에게 새 신발장이 생겼다. 가족이 많고 손님도 많아서 신발장은 금방 가득 찼다. 메이블은 사람들이 신발장에 신발을 넣고 꺼내는 모습을 주의 깊게 지켜봤다.

이 신발장은 특이하게도 선반마다 높이가 다르다. 첫 번째 선반은 바닥에서 h1h_1 높이에 있고, 두 번째 선반은 h2h_2 높이에 있다. 이런 식으로 nn번째 선반은 hnh_n 높이에 있다. 사람들이 신발을 놓고 꺼내는 방식을 살핀 메이블은 다음을 알아냈다. 키가 heightheight인 사람은 높이가 heightheight보다 큰 선반에는 신발 한 켤레를 놓을 수 없고, 높이가 height/kheight / k보다 작은 선반에도 놓을 수 없다. 또 키가 heightheight인 사람의 발 크기는 적어도 height/m1height / m_1 이상이고, 많아야 height/m2height / m_2 이하이다.

메이블은 신발장을 보고 일부 신발이 마법처럼 나타난 것 같다고 느낀다. 그녀가 관찰한 내용으로 보면, 누구도 그 신발을 거기에 놓을 수 없었다. 관찰 내용에 맞지 않는 신발 켤레의 수를 세어서 그녀의 확인을 도와라.

입력

첫 줄에 신발장의 선반 수 nn이 주어진다 (1≤n≤1051 \le n \le 10^5).

둘째 줄에 메이블이 도출한 계수 kk, m1m_1, m2m_2가 주어진다 (1≤k≤1001 \le k \le 100; 1≤m2≤m1≤1001 \le m_2 \le m_1 \le 100).

다음 nn개의 줄에 선반이 설명된다. ii번째 선반의 설명은 선반 높이 hih_i로 시작한다 (1≤h1≤1071 \le h_1 \le 10^7, 모든 i>1i > 1에 대해 hi−1<hi≤107h_{i-1} < h_i \le 10^7). 이어서 그 선반에 놓인 신발 켤레 수 kik_i가 주어진다 (1≤ki≤1051 \le k_i \le 10^5). 그 뒤에 그 선반의 신발 크기 sizei,jsize_{i,j}가 kik_i개 주어진다 (1≤sizei,j≤1071 \le size_{i,j} \le 10^7).

모든 kik_i의 합은 10510^5을 넘지 않는다.

출력

메이블의 관찰에 맞지 않는 신발 켤레의 수를 한 줄에 출력한다.

힌트

주어진 테스트에는 메이블의 관찰에 맞지 않는 신발 켤레가 정확히 두 개 있다. 높이 2인 선반에 있는 크기 1의 켤레와, 높이 4인 선반에 있는 크기 3의 켤레이다.

예제1

  1. 예제 1

    입력
    3
    2 1 1
    1 2 1 2
    2 2 1 4
    4 2 3 4
    
    예상 출력
    2