#2737. 电子对撞机

内存限制:256 MiB 时间限制:30 Sec

题目描述

  感谢HQ提供题目描述
  Q国最近科学技术不断进步,经过不懈努力,Q国主席QQ终于在质子对撞机的基础上研发了新一代能量供给装置:电子对撞机。
  这个设备呈长条状且对外封闭,设备内部有N个带有一定能量的电子。长条状的外形使得这些电子只能沿条形走向左右运动。设备长度为L,左端位置为0,右端位置为L。内部的电子速率恒定,每一个单位时间在左右方向上移动一个单位长度,而方向可能是向左或向右。当两个电子相遇即运动到同一个点时,它们之间会发生对撞,对撞后它们的速率不变但运动方向反向。设备的两个端点处(即坐标为0和L的位置)存在保护外壳,当电子运动到端点时会和外壳发生碰撞,碰撞后电子也会保持不变的速率但运动方向反向。电子分为高能电子和低能电子,电子之间对撞会产生能量,低能电子和低能电子对撞会产生1个单位的能量,低能电子和高能电子对撞会产生4个单位的能量,高能电子和高能电子对撞会产生25个单位的能量,电子和外壳碰撞不会产生能量。设备内部还有M个能量接收器,每个接收器可以接受从A到B的一个区间内(包括两个端点)的能量,且接收器可以接受的范围没有交集。若电子对撞的位置处于接收器的接受范围内,对撞产生的能量会被接收器接受,若对撞位置不在接收器上,这些能量则会丢失。这项技术的核心在于:对撞时电子的能量不会有损失,所以电子对撞机可以一直不断地运行下去供给能量。
  现在QQ已经制造出了第一批电子对撞机,并测得了时刻为0时电子的位置和运动状态,现在QQ想知道从时刻0到时刻T(包括T)总共接收到的能量,于是这个任务交给了神犇你。

输入格式

  第一行四个整数 N, M, L, T,分别表示电子个数,能量接收器个数,设备长度和时间。
  之后N行每行3个整数,Xi, Pi, Ei分别表示第i个电子的位置,运动方向和能量级别。
  Pi为1表示向右运动,为-1表示向左运动。
  Ei为0表示低能电子,为1表示高能电子。
  之后M行每行2个整数,Ai和 Bi,表示接收器的接收范围。

输出格式

  仅一行,包括一个整数,表示总共接收到的能量数。

样例

样例输入


			
3 1 8 7
2 1 0
4 -1 0
7 1 1
3 6

样例输出


			
5

样例说明
  T=1时,在位置3,第一个电子和第二个电子对撞,产生1的能量。
  在位置8,第三个电子和右侧外壳碰撞。
  T=3.5时,在位置5.5,第二个电子和第三个电子对撞,产生4的能量。
  T=4时,在位置0,第一个电子和左侧外壳碰撞。
  T=6时,在位置8,第三个电子和右侧外壳碰撞。
  T=6.5时,在位置2.5,第一个电子和第二个电子对撞,产生1的能量,由于在接收器范围外,能量丢失。
  最后结果为1+4=5个单位能量。

数据范围与提示