最近A学校正在实施教育改革。

一个学年由n天组成。A学校有m门课程，每天学生必须学习一门课，一门课程必须在一天内学习完。在学习完第i门课程后，学生们会收到 xixi 个家庭作业，其中 xi是区间[ai,bi]里的一个整数xi是区间[ai,bi]里的一个整数 。每门课还有一个属性，就是复杂度 cici 。A学校现在要制他们的课程表，具体要求如下：

·在课程表中，随着天数的增加，课程的复杂度是严格递增的。

·除了第1天，每天的作业量必须是前一天的k倍，或者比前一天多k个作业。（假设第i天的作业量为 xi，则对于i(1＜i≤n)到满足 x[i] ＝ k+x[i−1] 或 x[i] ＝ k⋅x[i−1]）；

现在，给定天数n，系数k，和m门课程的ai，bi，ci（1≤i≤m）。要求计算一个学年可以安排最大的总作业量( 总作业量的表达式是∑ni=1xi总作业量的表达式是∑i=1nxi )是多少。

单组测试数据
第一行，三个由空格隔开的整数n，m，k（1≤n≤m≤50，1≤k≤100），表示一个学年的天数，课程的数量，和作业增量系数。
接下来的m行，
每行有三个整数，ai，bi，ci（1≤ai≤bi≤10^16，bi-ai≤100，1≤ci≤100）
分别表示第i门课程的最小作业量，和最多作业量，以及复杂度。
不同的课程可以有相同的复杂度。课程编号从1到m。

如果有可行方案，第一行输出“YES”（没有引号），第二行输出最大的作业量。
如果没有可行方案，则输出一行“NO”（没有引号）。

xinjun