题目描述

一条南北主干道的长度为 $L$。第 $i$ 辆车从距离道路最南端 $d_i$ 的位置驶入，以初速度 $v_i$ 和加速度 $a_i$ 向北做匀加速运动。其中 $v_i>0$，$a_i$ 可以为正数、负数或 $0$。

当车辆到达道路最北端，即距离最南端为 $L$ 的位置，或车辆速度降为 $0$ 时，认为该车驶离主干道。

道路上设置了 $m$ 个测速仪，第 $j$ 个测速仪位于距离最南端 $p_j$ 的位置。每个测速仪都可以开启或关闭。一辆车经过开启的测速仪时，如果它的瞬时速度严格大于限速 $V$，就会被判定为超速。车辆驶入或驶出主干道的位置如果设有开启的测速仪，该测速仪也会进行测速。

请依次求出：

1. 所有测速仪均开启时，被判定为超速的车辆数量。
2. 在不漏掉上述任何一辆超速车辆的前提下，最多可以关闭多少个测速仪。

输入格式

本题原题采用文件读写，输入文件名为 detect.in，输出文件名为 detect.out。在 Hydro 上提交时，使用标准输入输出即可。

第一行包含一个正整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行包含四个整数 $n,m,L,V$，分别表示车辆数量、测速仪数量、道路长度和限速。
• 接下来 $n$ 行，每行包含三个整数 $d_i,v_i,a_i$，描述一辆车。
• 最后一行包含 $m$ 个严格递增的整数 $p_1,p_2,\ldots,p_m$，表示各测速仪的位置。

输出格式

对于每组测试数据，输出一行两个整数：第一个整数表示所有测速仪均开启时被判定为超速的车辆数量，第二个整数表示在不漏掉这些车辆的前提下最多可以关闭的测速仪数量。

样例

1
5 5 15 3
0 3 0
12 4 0
1 1 4
5 5 -2
6 4 -4
2 5 8 9 15

3 3

来源

CSP-S 2024 第 2 题

数据范围与提示

对于所有测试数据，保证：

• $1 \le T \le 20$。
• $1 \le n,m \le 10^5$，$1 \le L \le 10^6$，$1 \le V \le 10^3$。
• $0 \le d_i < L$，$1 \le v_i \le 10^3$，$|a_i| \le 10^3$。
• $0 \le p_1 < p_2 < \cdots < p_m \le L$。

• 特殊性质 A：所有 $a_i=0$。
• 特殊性质 B：所有 $a_i>0$。
• 特殊性质 C：所有 $a_i<0$，且所有车辆都不会在道路最北端驶离。