a290. TOI 2023/03 潛力組：借款金額

題目描述

你預計借入一筆非負整數金額，並在接下來 N 個月還款。第 i 個月最多可償還 Ai 元，銀行的利率指數為 R。

每個月先計息，再還款：若上個月還款後仍欠 X 元，本月先增加 X ÷ R 無條件進位至整數的利息，再以本月可用的還款金額償還。若可還款金額超過欠款，只需還清欠款；允許提早還清，之後不再產生欠款。

請求出能依這個計畫在 N 個月內還清的最大起始借款金額。

輸入格式

第一行有 N、R；第二行有 N 個整數，依序為 A1 到 AN。

• 1 ≤ N ≤ 200000
• 1 ≤ R ≤ 1000000000
• 0 ≤ Ai ≤ 1000000000

輸出格式

輸出一個非負整數，表示最大可借款金額。答案可能超過 32 位元整數範圍。

來源

TOI 2023 年 3 月潛力組〈借款金額〉。題意以自寫文字重述，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202303/loan.pdf