24546번 - 놀이기구에 진심인 편

문제

상원이는 놀이기구에 진심이다. 한 번 놀이공원에 가면 최소 $K$개의 놀이기구를 탈 때까지 절대 집에 돌아가지 않는다.

안타깝게도 상원이가 가장 좋아하는 놀이공원인 신촌테마파크에 새로운 안전 규정이 추가되었다. 신촌테마파크에는 $N$개의 놀이기구가 있는데 각각 키와 몸무게 제한이 생긴 것이다. 입장 시 정수로 작성해서 낸 키와 몸무게가 각 놀이기구의 제한을 벗어나면 이용할 수 없다.

하지만 누구보다 놀이기구에 진심인 상원이는 다 생각이 있다. 바로 키와 몸무게를 속이는 것이다. 다만, 실제 키 $H,ドル 몸무게 $W$와 차이가 너무 크면 들킬 수 있기 때문에 최대 $D$만큼만 조작하기로 했다. 다시 말하면, $H-D \le h \le H+D$이고 $W-D \le w \le W+D$를 만족하는 정수 $h,ドル $w$를 키와 몸무게로 작성해서 낼 것이다.

이때 상원이가 신촌테마파크에서 최소 $K$개의 놀이기구를 탈 수 있는 ($h,ドル $w$)쌍의 개수를 구해보자.

입력

첫 번째 줄에 $N,ドル $K,ドル $H,ドル $W,ドル $D$가 정수로 주어진다. (1ドル \le N, K, H, W, D \le 100,000円$)

두 번째 줄부터 $N$개의 줄에 정수 $h_{lo}, h_{hi}, w_{lo}, w_{hi}$가 주어진다. 놀이기구의 키 제한이 $h_{lo}$이상 $h_{hi}$이하, 몸무게 제한이 $w_{lo}$이상 $w_{hi}$이하라는 의미이다. (1ドル \le h_{lo} \le h_{hi} \le 100,000円,ドル 1ドル \le w_{lo} \le w_{hi} \le 100,000円$)

출력

상원이가 신촌테마파크에서 최소 $K$개의 놀이기구를 탈 수 있는 ($h,ドル $w$)쌍의 개수를 출력한다.

제한

힌트