###### 第九屆高一生程式設計排名賽

# E. 劫富濟貧

<center> 出題者 : 511</center>
<center>Time : 1s</center>
<center>Memory : 256MiB</center>
</br>

無名是一位嫉惡如仇的俠士，平生最喜歡替別人打抱不平。
這天他來到一個小鎮，發現鎮上貧富差距極大，官兵貪汙、奸商肆虐，在這些人富得流油之時，卻又另一群底層農民受到龐大賦稅壓榨，一貧如洗，生活難以維持。
於是無名決定劫富濟貧，以維持正義。
這個鎮上居住著N種不同階級的人，同一階級持有相同的黃金數，每天夜裡他會潛入當天鎮上最富有的人家中，盜取他一半的黃金，然後把這些黃金分給窮人，分配每單位黃金時會優先給當時黃金數最少的人，如此可使最後整個鎮上最貧窮的人持有的黃金數比其他分法多。
然而他不久後必須離開去參加武林大會，最多只能在這個小鎮待D個晚上，請問最後鎮上的貧富差距(最富有的人持有黃金數-最貧窮的人持有黃金數)是多少?

## 輸入說明
單筆輸入
第一行輸入兩個正整數N、D，表示鎮上的階級數及無名待在鎮上的天數。
第二行有N個數字$C_i$，表示第i個階級每人持有的黃金數。
第三行有N個數字$P_i$,表示第i個階級的總人數。

## 輸出說明
輸出一個整數，表示鎮上的貧富差距。

## 輸入限制
* $N\le 10^5$
* $D\le 10^{18}$
* $0\le C_i\le 10^9$
* $1\le P_i\le 10^4$

## 子任務

| Subtask | Score | Contraints
|-|-|-
| 1 | 20 | 所有輸入數字不超過100
| 2 | 35 | 對於所有$1\le i\le N,P_i=1$
| 3 | 45 | 無特殊限制

## 範例輸入 1

5 3
1 2 3 4 5
5 4 3 2 1

## 範例輸出 1

1

## 附註
有多個人最富有的話會隨機挑一個人，也有可能把偷來的黃金送回給被偷的人。
如果某人有2k+1單位的黃金，則被偷走k單位，剩下k+1單位。