Johnny is at a carnival which has n raffles. Raffle i has a prize with value p i . Each participant can put tickets in whichever raffles they choose (they may have more than one ticket in a single raffle). At the end of the carnival, one ticket is selected at random from each raffle, and the owner of the ticket wins the associated prize. A single person can win multiple prizes from different raffles. However, county rules prevent any one participant from owning more than half the tickets in a single raffle, i.e. putting more tickets in the raffle than all the other participants combined. To help combat this (and possibly win some prizes), the organizers started by placing a single ticket in each raffle, which they will never remove. Johnny bought t tickets and is wondering where to place them. Currently, there are a total of l i tickets in the i -th raffle. He watches as other participants place tickets and modify their decisions and, at every moment in time, wants to know how much he can possibly earn. Find the maximum possible expected value of Johnny's winnings at each moment if he distributes his tickets optimally. Johnny may redistribute all of his tickets arbitrarily between each update, but he may not place more than t tickets total or have more tickets in a single raffle than all other participants combined. The first line contains two integers n , t , and q ( 1 ≤ n , t , q ≤ 200 000 ) — the number of raffles, the number of tickets Johnny has, and the total number of updates, respectively. The second line contains n space-separated integers p i ( 1 ≤ p i ≤ 1000 ) — the value of the i -th prize. The third line contains n space-separated integers l i ( 1 ≤ l i ≤ 1000 ) — the number of tickets initially in the i -th raffle. The last q lines contain the descriptions of the updates. Each description contains two integers t k , r k ( 1 ≤ t k ≤ 2 , 1 ≤ r k ≤ n ) — the type of the update and the raffle number. An update of type 1 represents another partici