Description

一个有N(1<=N<=16000)个木板的栅栏

由K(1<=k<=100)个工人粉刷． 一开始每个工人坐在编号为Si的木板前． 每个工人只能粉刷一串连续的，不大于Li，并且包含Si的木板． 第i个工人每粉刷一块木板的工钱为Pi(1<=Pi<=10000) 求得所有工人最多能得到的工钱

Format

Input

第一行给出N,k 接下来N行，每行给出Li,Pi,Si

Output

如题

Samples

８　４
３　２　２
３　２　３
３　３　５
１　１　７

17