0 Judge
Code: 0
拓猶它是一家組織嚴謹的公司,除了最基層的員工外,每個人都會恰好有兩個直接下屬;除了最上層的員工外,每個人都只會有一個直接上司。如果我們將上司-下屬的關係畫作一張圖,更會發現他構成了一個 $k$ 層、$2^k-1$ 個節點的滿二叉樹。
今年公司業績暴漲,股東們決定發給員工們獎金,發放的方式是將一大筆錢發給最上層的員工,他會先自己拿取一些錢,再將剩下的錢交給他的直接下屬,他的兩個直接下屬自己拿取一些錢,再將剩下的錢交給他們各自的直接下屬 ... 以此類推。
由於公司有規定每一個員工可以從上司得到的金額上限。現在想要請問在股東所給的獎金充足的條件下,最基層的員工拿到的獎金總和最多是多少?
為了簡化問題,我們將每個員工編號:最上層的員工編號為 $1$ ,對於每個不是最基層的員工,如果他的編號是 $x$ ,那麼他的兩個直接下屬的編號是 $2x$ 以及 $2x+1$ 。
第一行有一個正整數 $k (2\le k\le 25)$ ,代表二叉樹的層數。
接著會有 $4$ 個正整數 $a,b,c,d (1\le a,b,c,d \le 10^8)$,用來描述員工可以從上司得到的金額上限的參數。
編號是 $2$ 的員工可以從上司得到的金額上限是 $d\pmod{c}$,編號是 $3$ 的員工可以從上司得到的金額上限是 $a\cdot d+b\pmod{c}$ ...。對於 $2< i\le 2^k-1$,如果編號 $i-1$ 號員工的金額上限是 $X$ ,那麼編號 $i$ 號員工的金額上限是會是 $a\cdot X+b\pmod{c}$。
請輸出最基層的員工拿到的獎金總和最多是多少。
3
4 2 9 5
6
最底基層的員工拿到的獎金總和最大的情況可能是: $0,2,1,3$ 或是 $0,2,0,4$