砍樹 (APCS 2020-01 中高級)

\(N\) 棵樹種在一條從座標 \(0\) 到座標 \(L\) 的線段上。第 \(i\) 棵樹的位置是 \(c_i\)，高度是 \(h_i\)。

現階段要砍一棵尚未砍除的樹時，必須選擇讓它向左或向右倒下。若向左倒下，它會覆蓋區間 \([c_i-h_i,c_i]\)；若向右倒下，它會覆蓋區間 \([c_i,c_i+h_i]\)。倒下的區間不可超出 \([0,L]\)，而且區間內不可有其他尚未砍除的樹。若其他樹剛好在倒下區間的端點，不算被壓到。

你可以不斷選擇一棵目前可以砍除的樹，將它砍倒並移除，直到沒有任何樹可以砍除為止。可以證明，無論砍樹順序為何，最後能被砍除的樹木集合都相同。

請輸出最後能砍除的樹木數量，以及這些樹木中最高的高度。

輸入格式

第一行包含兩個整數 \(N\)、\(L\)，代表樹木數量與右邊界座標。

第二行包含 \(N\) 個整數 \(c_1,c_2,\ldots,c_N\)，代表每棵樹的位置，並且已由小到大排序。

第三行包含 \(N\) 個整數 \(h_1,h_2,\ldots,h_N\)，代表每棵樹的高度。

限制

• \(1 \le N \le 10^5\)
• \(1 \le L \le 10^9\)
• \(0 \le c_1 < c_2 < \cdots < c_N \le L\)
• \(1 \le h_i \le 10^9\)

輸出格式

第一行輸出最後能被砍除的樹木數量。

第二行輸出能被砍除的樹木中最高的高度；若沒有任何樹能被砍除，請輸出 0。

評分說明

• 30 分：\(N \le 1000\)
• 70 分：無額外限制

範例輸入

6 140
10 30 50 70 100 125
30 15 55 10 55 25

範例輸出

4
30

範例解釋

一種可行順序是砍除第 \(2\)、第 \(4\)、第 \(6\)、第 \(1\) 棵樹。最後共砍除 \(4\) 棵，最高高度為 \(30\)。

題目來源

APCS 2020 年 1 月程式實作題第 3 題「砍樹」，亦收錄於 ZeroJudge h028。