题号：NC19818
时间限制：C/C++/Rust/Pascal 15秒，其他语言30秒
空间限制：C/C++/Rust/Pascal 8 M，其他语言16 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 15秒，其他语言30秒
空间限制：C/C++/Rust/Pascal 8 M，其他语言16 M
64bit IO Format: %lld
题目描述
终于活成了自己讨厌的样子。
暖婊是个垃圾游戏。栗子米是个贫困少女。
为了掏空你的钱包，在接下来n天，暖婊会有m个活动，一个活动在第l天到第r天之间，在这几天中，你只要充一元钱就能获得这个活动中的y件衣服。同时每个活动有个也有个上限x，也就是说如果你氪了k元钱，那么你能获得*y)
件衣服。
如果很多个活动有交集，那么你在那天充的钱会被算入所有的活动中。我们认为每天只能充整数的钱。
栗子米一共有c块钱，问栗子米最多一共能混到多少件衣服。
本题内存限制为8MB，请选手们注意，合理挑选语言。
暖婊是个垃圾游戏。栗子米是个贫困少女。
为了掏空你的钱包，在接下来n天，暖婊会有m个活动，一个活动在第l天到第r天之间，在这几天中，你只要充一元钱就能获得这个活动中的y件衣服。同时每个活动有个也有个上限x，也就是说如果你氪了k元钱，那么你能获得
如果很多个活动有交集，那么你在那天充的钱会被算入所有的活动中。我们认为每天只能充整数的钱。
栗子米一共有c块钱，问栗子米最多一共能混到多少件衣服。
本题内存限制为8MB，请选手们注意，合理挑选语言。
输入描述:
第一行一个整数T(T≤ 100)，表示数据组数。
每组数据第一行三个正整数n,m,c(1≤ n,m≤ 2000,1≤ c≤ 104)，表示天数和活动数和初始的钱数。
接下来m行，每行四个整数l,r,x,y(1≤ l≤ r≤ n, 1≤ x≤ 104, 1≤ y≤ 106)，表示一个活动的四个参数。
保证至多5组数据满足n,m≥ 100。
输出描述:
对于每组数据，输出一行表示答案。