User's AC Ratio

50.0% (3/6)

Submission's AC Ratio

24.5% (62/253)

Tags

Description

本題與桑京邀請賽完全相同,但是請小心邪惡的測資範圍和記憶體限制(當然,這裡不會有"lib1995.h"這個標頭檔)。

注意:由於本題輸入/輸出十分龐大,使用C++作答的同學,請在程式碼開頭加上#include <cstdio>,並利用scanf讀入資料、用printf輸出資料
若你使用了<iostream><bits/stdc++.h>標頭檔,極有可能會因為效率太差以致於程式執行時間、空間超過限制。
如果你需要使用<bits/stdc++.h>,請在引入該標頭檔前加上一行#define _GLIBCXX_IOSTREAM,以避免<iostream>的引入。

Input Format

輸入格式同桑京邀請賽

對於所有測資,$a_i, b_i\leq N\leq 2\times 10^ 5; M\leq 2\times 10^ 5; s_i\leq 10^ 9$。

子任務(測資) 額外限制 分數
1 (0~5) $N,M\leq 10^ 4$ 49
2 (0~11) 無限制 51

Output Format

輸出格式同桑京邀請賽

Sample Input

6 3
1 4
5 5
3 6
7 3 13 6 1 18

Sample Output

13
1
18

Hints

你有看過記憶體限制這麼小的題目嗎?如果沒有,那麼
你現在看過了(X)是不是應該要想一些比較不正常的做法呢?

Problem Source

Problem Set by Yihda Yol

Subtasks

For Testdata: 0 ~ 5, Score: 49
For Testdata: 0 ~ 11, Score: 51
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1800 4448 262144
1 1800 4448 262144
2 1800 4448 262144
3 1800 4448 262144
4 1800 4448 262144
5 1800 4448 262144
6 1800 4448 262144
7 1800 4448 262144
8 1800 4448 262144
9 1800 4448 262144
10 1800 4448 262144
11 1800 4448 262144