题目描述

学校田径队正在参加跑步接力赛。队伍中共有 $n$（$2 \leq n \leq 10^4$）名成员。为了让每个人都参与比赛，每位成员至少需要跑 $d$（$0 \leq d \leq 10$）米。除此之外，每个人可以跑任意距离。跑道的总长度为 $L$（$1 \leq L \leq 10^5$）米。

对于队伍中的第 $i$ 名成员：

• 如果他心情好，则跑一米需要 $t_i$ 秒（$1 \leq t_i \leq 4 \times 10^4$）。
• 如果他心情差，则跑一米需要 $s_i$ 秒（$1 \leq s_i \leq 4 \times 10^4$，且 $1 \leq t_i \leq s_i$）。

作为队伍的教练，你可以提前分配每位成员的跑步距离。假设：

• 如果所有成员心情都差，队伍完成接力赛的总时间为 $S$ 秒。
• 如果所有成员心情都好，队伍完成接力赛的总时间为 $T$ 秒。

你希望取得一个好成绩，但同时不希望在某些成员心情差时成绩太糟糕。因此，你希望在满足 $S \leq W$（$1 \leq W \leq 2147483647$）的条件下，求出 $T$ 的最小值。

输入格式

输入以一行整数开始，表示测试用例的数量。测试用例不超过 $100$ 个。

对于每个测试用例：

• 第一行包含四个整数：$n$、$d$、$L$ 和 $W$。
• 接下来的 $n$ 行，每行表示一名成员，包含两个整数 $s_i$ 和 $t_i$，分别表示该成员心情差和心情好时跑一米所需的时间。

输出格式

对于每个测试用例：

• 如果无法找到合适的分配方案，输出一行"No solution"。
• 否则，输出 $T$ 的最小值（保留两位小数）。

样例输入 1

2
2 1 20 141
8 3
6 6
3 8 20 200
8 3
6 6
7 1

样例输出 1

88.50
No solution

来源

福州$2011$