Raj 有一条物理网络线路将他的办公室连接到互联网。该线路带宽为每毫秒 $$$b$$$ 字节。
有 $$$n$$$ 用户想要使用这条网络线路传输一些数据。其中第 $$$i$$$ 将使用从毫秒 $$$s_i$$$ 到毫秒 $$$f_i$$$ 的行(包括毫秒 $$$f_i$$$)。他的初始数据速率将设置为 $$$d_i$$$。这意味着他将使用等于$$$d_i$$$的数据速率,持续毫秒$$$s_i$$$,然后它将根据下面描述的过程进行更改。
流量控制将发生如下。假设有 $$$m$$$ 用户尝试在毫秒 $$$x$$$ 内通过给定的网络线路传输一些数据。将这些$$$m$$$用户中的第$$$i$$$用户在该毫秒开始时的数据速率表示为$$$t_i$$$。所有 $$$t_i$$$ 都是非负整数值。
1. 如果 $$$m = 0$$$,i。 e.在这一毫秒内没有用户尝试传输数据,什么也没有发生。
2. 如果所有 $$$t_i$$$ 的总和小于或等于 $$$b$$$,则每个活动用户成功完成其传输(第 $$$i$$$ 个活动用户传输 $$$t_i$$$ 字节)。此后,每个活跃用户的数据速率增长 $$$1$$$,即。 e.每个 $$$t_i$$$ 增加 $$$1$$$。
3. 如果所有$$$t_i$$$ 的总和大于$$$b$$$,则发生拥塞,并且在这一毫秒内根本没有数据传输成功。如果发生这种情况,每个 $$$t_i$$$ 都会减少两次,i。 e.每个 $$$t_i$$$ 均替换为 $$$\lfloor \frac{t_i}{2} \rfloor$$$。
Raj知道所有值$$$n$$$、$$$b$$$、$$$s_i$$$、$$$f_i$$$和$$$d_i$$$,他想计算所有用户传输的总字节数。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$b$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq b \leq 10^9$$$),分别表示将使用线路的用户数量和线路带宽。
以下 $$$n$$$ 行包含三个整数 $$$s_i$$$、$$$f_i$$$ 和 $$$d_i$$$ ($$$1 \leq s_i \leq f_i \leq 10^9$$$、$$$1 \leq d_i \leq 10^9$$$),表示第 $$$i$$$ 个用户将尝试在 $$$s_i$$$ 和 $$$f_i$$$(含)之间的每毫秒内传输数据,以及第 $$$i$$$ 个用户的初始数据速率。
输出
打印一个整数 — 所有用户将成功传输的字节总数。
示例
输入 #1
1 3 1 5 2
输出 #1
10
输入 #2
1 10 7 11 1000
输出 #2
0
输入 #3
2 6 1 12 1 8 20 3
输出 #3
64
输入#4
3 10 1 100 1 30 60 20 40 80 6
输出#4
534
注意
考虑第一个例子。
- 毫秒 $$$1$$$:用户 $$$1$$$ 传输 $$$2$$$ 字节。
- 毫秒 $$$2$$$:用户 $$$1$$$ 传输 $$$3$$$ 字节。
- 毫秒$$$3$$$:发生拥塞,没有用户传输数据。
- 毫秒 $$$4$$$:用户 $$$1$$$ 传输 $$$2$$$ 字节。
- 毫秒 $$$5$$$:用户 $$$1$$$ 传输 $$$3$$$ 字节。
在第二个示例中,从第 $$$7$$$ 到第 $$$11$$$(含)的每一毫秒,都会发生拥塞,并且唯一的用户将其速率降低两次。然而,它们在断开连接之前不会降低足够的速度。
考虑第三个例子。
- 毫秒 $$$1$$$:用户 $$$1$$$ 传输 $$$1$$$ 字节。
- 毫秒 $$$2$$$:用户 $$$1$$$ 传输 $$$2$$$ 字节。
- 毫秒 $$$3$$$:用户 $$$1$$$ 传输 $$$3$$$ 字节。
- 毫秒 $$$4$$$:用户 $$$1$$$ 传输 $$$4$$$ 字节。
- 毫秒 $$$5$$$:用户 $$$1$$$ 传输 $$$5$$$ 字节。
- 毫秒 $$$6$$$:用户 $$$1$$$ 传输 $$$6$$$ 字节。
- 毫秒$$$7$$$:发生拥塞,没有用户传输数据。
- 毫秒 $$$8$$$:用户 $$$1$$$ 传输 $$$3$$$ 字节。用户$$$2$$$传输$$$3$$$字节。
- 毫秒$$$9$$$:发生拥塞,没有用户传输数据。
- 毫秒 $$$10$$$:用户 $$$1$$$ 传输 $$$2$$$ 字节。用户$$$2$$$传输$$$2$$$字节。
- 毫秒 $$$11$$$:用户 $$$1$$$ 传输 $$$3$$$ 字节。用户$$$2$$$传输$$$3$$$字节。
- 毫秒$$$12$$$:发生拥塞,没有用户传输数据。
- 毫秒 $$$13$$$:用户 $$$2$$$ 传输 $$$2$$$ 字节。
- 毫秒 $$$14$$$:用户 $$$2$$$ 传输 $$$3$$$ 字节。
- 毫秒 $$$15$$$:用户 $$$2$$$ 传输 $$$4$$$ 字节。
- 毫秒 $$$16$$$:用户 $$$2$$$ 传输 $$$5$$$ 字节。
- 毫秒 $$$17$$$:用户 $$$2$$$ 传输 $$$6$$$ 字节。
- 毫秒$$$18$$$:发生拥塞,没有用户传输数据。
- 毫秒 $$$19$$$:用户 $$$2$$$ 传输 $$$3$$$ 字节。
- 毫秒 $$$20$$$:用户 $$$2$$$ 传输 $$$4$$$ 字节。