6475：商业竞争

在这里你需要解决一个全世界人类从诞生起就面临的最大的问题——如何发大财。

你是一名电视广告市场的中介。你的工作是给要打广告的公司安排一天的时间去播放他们的广告。这家公司一共拍摄了$n$个广告片段，每个片段最多只能播放一次，第$i$个片段需要占据$w_i$秒的档期，在第$k$天这个片段给这家公司带来的净利润为$k\times a_i+b_i$。一个片段一旦开始播放就不能掐断。

你需要在$[l,r]$之间选择一个正整数$k$，在第$k$天播放这家公司的广告。这家公司在你告知$k$后，会斟酌着选择一些广告进行播放，使得他们的总收益最大(也可能一个广告都不播放，如果都是负收益的话)。电视每天最多只能播放总长度不超过$m$秒的广告，所以当档期不足时，他们也会酌情舍弃一些广告。

商业竞争是残酷的，对方赚的越多，你赚的就越少。请选择一个最合适的$k$，使得该公司按照最优策略投放广告的总收益最小。

第一行包含一个正整数$T(1\leq T\leq 10)$，表示测试数据的组数。

每组数据第一行包含四个正整数$n,m,l,r(1\leq n,m\leq 500,1\leq l\leq r\leq 10^6)$，分别表示广告片段的数量、档期的限制以及选择的范围。

接下来$n$行，每行三个整数$a_i,b_i,w_i(-10^6\leq a_i\leq 10^6,-10^{12}\leq b_i\leq 10^{12},1\leq w_i\leq m)$，依次描述每个广告片段。

对于每组数据输出一行一个整数，即该公司按照最优策略投放广告的总收益的最小可能值。