955
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小a作为955公司的老板，每天还会给员工买k个鸡腿。一共有n家店可以选择。由于某些奇怪的原因，第x天第i家店的鸡腿单价为（可能为负，表示你买鸡腿还会回报你一些钱），且每天只提供最多t_i个鸡腿。
每一天可以在商店i内购买任意多（但不超过给定的t_i）个鸡腿。你需要帮助小a确定连续m天的购买方案，使得每天的花费最小。输出每一天的最小花费。

输入描述:

第一行三个正整数n,m,k，分别表示商店数量、天数、每天所需购买的鸡腿数量。
接下来n行，每行四个整数a_i,b_i,c_i,t_i，如题目描述所述，表示第i家店的参数。

输出描述:

输出m行。每行一个整数，表示每天的最小花费。
示例1

输入

复制 
3 3 3
-1 3 1 2
-1 4 -1 2
-1 1 4 2

输出

复制 
7
14
-9

备注:

。保证。
输入数据量可能较大，建议使用较快的读入方式。
其实小a觉得，每周工作三天，每天工作四小时就很好了。