Farmer John 有 M 头奶牛，为了方便，编号为 1,\dots,M。这些奶牛平时都吃青草，但是喜欢偶尔换换口味。Farmer John 一天烤了 N 个派请奶牛吃，这 N 个派编号为 1,\dots,N。第 i 头奶牛喜欢吃编号在 [l_i,r_i] 中的派（包括两端），并且没有两头奶牛喜欢吃相同范围的派。第 i 头奶牛有一个体重 w_i，这是一个在 [1,10^6] 中的正整数。
Farmer John 可以选择一个奶牛序列c_1,c_2,...,c_K,并让这些奶牛按这个顺序轮流吃派。不幸的是，这些奶牛不知道分享！当奶牛吃派时，她会把她喜欢吃的派都吃掉——也就是说，她会吃掉编号在 [l_i,r_i]中所有剩余的派。
Farmer John 想要避免当轮到一头奶牛吃派时，她所有喜欢的派在之前都被吃掉了这样尴尬的情况。因此，他想让你计算，要使奶牛按 c_1,c_2,\dots,c_K的顺序吃派，轮到这头奶牛时她喜欢的派至少剩余一个的情况下，这些奶牛的最大可能体重总和是多少。