小藍打算采購 n 種物品，每種物品各需要 1 個。

小藍所住的位置附近一共有 m 個店鋪，每個店鋪都出售著各種各樣的物品。

第 i 家店鋪會在第 s_i 天至第 t_i 天打折，折扣率為 p_i，對于原件為 b 的物品，折后價格為。其它時間需按原價購買。

小藍很忙，他只能選擇一天的時間去采購這些物品。請問，他最少需要花多少錢才能買到需要的所有物品。

題目保證小藍一定能買到需要的所有物品。

輸入的第一行包含兩個整數 n, m，用一個空格分隔，分別表示物品的個數和店鋪的個數。

接下來依次包含每個店鋪的描述。每個店鋪由若干行組成，其中第一行包含四個整數 s_i , t_i , p_i , c_i，相鄰兩個整數之間用一個空格分隔，分別表示商店優(yōu)惠的起始和結束時間、折扣率以及商店內的商品總數。之后接 c_i 行，每行包含兩個整數 a_j , b_j ，用一個空格分隔，分別表示該商店的第 j 個商品的類型和價格。商品的類型由 1 至 n 編號。

輸出一行包含一個整數表示小藍需要花費的最少的錢數。

2 2
1 2 89 1
1 97
3 4 77 1
2 15

101

對于 40% 的評測用例，n, m ≤ 500 ，s_i ≤ t_i ≤ 100 ， ∑ c_i ≤ 2000 ；

對于 70% 的評測用例，n, m ≤ 5000 ， ∑ c_i ≤ 20000 ；

對于所有評測用例，1 ≤ n, m ≤ 100000 ，1 ≤ c_i ≤ n ， ∑ c_i ≤ 400000 ， 1 ≤ s_i ≤ t_i ≤ 10⁹ ，1 < p_i < 100 ，1 ≤ a_j ≤ n ，1 ≤ b_j ≤ 10⁹ 。

本試題適用于用c/c++/java代碼來完成，如用Python代碼出現時間超限問題建議轉到：http://www.sztianhecheng.cn/oj/problem2730.html鏈接