Dakimakura Distribition | CodeChef Solution

Hello coders, today we are going to solve Dakimakura Distribution CodeChef Solution whose Problem Code is DAKIMAKU.

Task

Only a few centuries later, the Berland government realized what was necessary for the country’s prosperity. That’s right, a dakimakura for every resident of Berland!

It is known that Berland consists of N cities, where C_i people live in city i and it takes T_i hours to get from city i to city i + 1.

The government is ready to allocate x tugriks for the implementation of the project to give out dakimakuras. They also agreed with local producers, so the dakimakuras themselves are free.

To implement the project, the government can open a branch for issuing dakimakuras free of charge in several cities. For each city with an open branch for issuing dakimakuras, the government can pay 1 tugrik to increase its productivity by 1 unit. It can be increased any number of times, so that a productivity of k units costs k tugriks.

Then the issuance of dakimakuras begins. For each resident of the country that is located in city i, he/she will travel to the first city with index greater or equal to i that has a branch. Recall, it takes Ti hours to travel from city i to i+1. After arrival, he/she enters the queue in the branch.

For each branch, it handles the queue as follows.

• Let the productivity of this branch be p. If there are less than p people in the queue, then the branch issues dakimakuras to everyone in the queue. Otherwise, it starts with the first p people, and gives them dakimakuras. A branch can only give dakimakuras every hour (that is, integer times since the start). Also, a resident cannot receive a dakimakura at the same moment he/she enters the queue.

You must find the minimum amount of time required for the government to issue dakimakuras to all residents of Berland, spending no more than x tugriks in total. Assume all the residents start travelling at the same time, and the branches also opened at hour 0.

Input

• The first line contains a single integer t – the number of test cases. Then t test cases follow.
• The first line of each test case contains two integers N and x – the number of cities in Berland and the maximum amount of tugriks that the government can spend.
• The second line contains N integers C₁, . . . , C_n.
• The third line contains N − 1 integers T₁, . . . ,T_n−1.

Output

For each test case, print in a single line the answer to the problem.

Constraints

• 1 ≤ t ≤ 5
• 2 ≤ N ≤ 100
• 1 ≤ x ≤ 10⁹
• 0 ≤ C_i ≤ 10⁹
• 1 ≤ T_i ≤ 10⁹

Subtasks

• Subtask 1 (20 points): 2 ≤ N ≤ 8, 1 ≤ x, T_i ≤ 8 and 0 ≤ C_i ≤ 8
• Subtask 2 (20 points): x = 1
• Subtask 3 (40 points): 2 ≤ N ≤ 40
• Subtask 4 (20 points): Original constraints

Sample Input

2
5 6
8 3 1 5 0
1 1 1 1
5 1
2 8 0 0 1
7 3 1 2

Sample Output

3
16

Explanation

The first test case:

Let’s open a branch in city 1 with productivity 3 and one in city 4 with productivity 3.

Then in the 0-th hour, 8 people in city 1 and 5 people in city 4 will enter the queues in their respective cities. Meanwhile, the people in cities 2 and 3 will travel to the next city.

Then in the 1-st hour, 3 people in city 1 and 3 people in city 4 will receive dakimakuras. Now the numbers of remaining people in each city are [5, 0, 3, 3, 0].

Then in the 2-nd hour, 3 people in city 1 and 3 people in city 4 will receive dakimakuras. Now the numbers of remaining people in each city are [2, 0, 0, 3, 0].

Then in the 3-rd hour, 2 people in city 1 and 3 people in city 4 will receive dakimakuras. Now, every resident in Berland has received a dakimakura, so the process took 3 hours.

Solution – Dakimakura Distribition

C++

Python

Java

Disclaimer: The above Problem (Dakimakura Distribition) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.