TopCoder

Thumb output jddoia
$\huge 南ことり$
今天也要輸贏!?

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

66.7% (2/3)

Description

大家有看過去年 NPSC 決賽時高中組的背包問題嗎?如果你沒看過的話,現在讓你看看。

身為一個打競賽的人,如果背上背著一個能夠負重 $W$ 的空背包,然後身旁有 $N$ 個物品,並且每個物品都有各自的權重和價值的話,想必一定會開始在腦中模擬一次背包問題吧。
現在,你就面臨著這種狀況。但是你覺得如果這只是一個普通的背包問題,那麼一點挑戰性都沒有,於是你決定讓問題困難一點。
對於你身旁的每個物品,你可以選擇不把它整個放進背包,而是切下一部分放進背包。假設第 $i$ 個物品原本的重量是 $w_i$、價值是 $v_i$,那麼切下 $w'$($0 \leq w' \leq w_i$)之後,物品的價值就會是 $v_i \cdotp w' / w_i$。但是因為把東西切下一部分很累,所以對於第 $i$ 個物品,你可以花費 $c_i$ 的代價請你的隊友幫你切。
問題非常簡單,請你算出對於所有可能的切東西、背包裡裝著的東西的方法中,$V-C$ 的最大值,其中 $V$ 是包包裝著的物品們的總價值,而你花了 $C$ 的代價請隊友幫你切東西。

比賽結束之後,雖然你如願解出了這個問題,但是你開始思考,如果現在物品的切割費用會改變,那答案會有什麼變化?

正式地說,你會有 $Q$ 個好奇的修改,其中第 $i$ 次的修改是第 $x_i$ 個物品的切割代價變成了 $d_i$。請在第一次修改之前以及每一次修改之後,輸出 $V-C$ 的最大值,$V$ 與 $C$ 的意義與原題相同。

為了滿足你自己的好奇心,解答你自己的問題吧。

Input Format

第一行有一個正整數 $T$,代表總共有幾筆測試資料。
之後每一筆測資的第一行包含兩個正整數 $N, W$。
之後的 $N$ 行,第 $i$ 行會有三個整數,代表 $w_i, v_i, c_i$。
在這之後的一行有一個正整數 $Q$。
之後會有 $Q$ 行,第 $i$ 行會有兩個整數,代表 $x_i, d_i$。

  • $T \in \{1, 31\}$
  • $N \leq 1000$
  • $W, Q \leq 2000$
  • $1 \leq w_i \leq 2000$
  • $1 \leq v_i, c_i, d_i \leq 2000$
  • $1 \leq x_i \leq N$

Output Format

請輸出 $(Q+1)$ 行,依序為第一次修改前的答案、每一次修改後的答案。你輸出的數字跟答案只要相對誤差或絕對誤差在 $10^ {-6}$ 以內都算正確。

Sample Input

1
1 30
1 1 1
1
1 2

Sample Output

1.00
1.00

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 262144 262144 1