C Programmes

QUE➤ Chef has recently got a broadband internet connection. His history of internet data usage is provided as below.

During the first T₁ minutes, the internet data used was D₁ MBs per minute, and during the next T₂ minutes, it was D₂ MBs per minute, and so on till during last T_N minutes it was D_N MBs per minute.

The internet provider charges the Chef 1 dollar for every 1 MB data used, except for the first K minutes, when the internet data is free as part of the plan provided to Chef.

Please find out the total amount that Chef has to pay the internet provider (in dollars).

Input

First line of the input contains a single integer TC the number of test cases. Description of TC test cases follow.

First line of each test case contains two space separated integers N and K.

Next N lines of each test case contains information about the internet data usage. Specifically, in the i-th line, there will be two space separated integers: T_i and D_i.

Output

For each test case output a single integer in separate line, the amount that Chef has to pay in dollars.

Example

Explanation

Example case 1. For the first two minutes, internet data of usage of Chef is free. He has to pay for last 2 minutes only, for which he will be charged at 3 dollars per minute, i.e. total 6 dollars.

Example case 2. For the first two minutes, internet data of usage of Chef is free. He has to pay for last 1 minute only, for which he is being charged at 3 dollars per minute. So, in total he has to pay 3 dollars.

Example case 3. This time, Chef is not provided any free data usage. He has to pay for entire data usage, which comes out to be 1 * 2 + 2 * 4 + 10 * 10 = 110 dollars.

SOLUTION 1 FOR UNDERSTAND:- https://docs.google.com/document/d/1QB2dgq5NZwshOLv3NGlaXOEhKFLyPS1_du9idcxCF9E/edit?usp=sharing
SOLUTION 2:- https://docs.google.com/document/d/1HXHTPEenb9JU3hWQJOUHT5Zt-3Y_Hpmc9qzPkFF9yDw/edit?usp=sharing

REFERENCE:-https://www.codechef.com/problems/DWNLD

FOLLOW ME ON :-

INSTAGRAM :- https://www.instagram.com/akshay_methaniya_2809/

YOUTUBE :- https://www.youtube.com/channel/UCDbGAU0c_78ue2IXi6ibtYQ

FACEBOOK :- https://www.facebook.com/akshay.methaniya

Comments

Kruskal’s Minimum Spanning Tree Algorithm & Programme

PROBLEM : Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step. To understand Kruskal's algorithm let us consider the following example − Step 1 - Remove all loops and Parallel Edges Remove all loops and parallel edges from the given graph. In case of parallel edges, keep the one which has the least cost associated and ove all others. Step 2 - Arrange all edges in their increasing order of weight The next step is to create a set of edges and weight, and arrange them in an ascending order of weightage (cost). Step 3 - Add the edge which has the least weightage Now we start adding edges to the graph beginning from the one which has the least weight. Th...

Adaptive Software Development (ASD)

Adaptive Software Development (ASD) :- Adaptive Software Development(ASD) has been proposed by Jim High smith as technique for building complex software and system. ASD focus on human collaboration and team self-organization. Jim High smith defines an ASD "Life Cycle" that consist of three phases Speculation Collaboration learning During speculation, the project is initiated and adaptive cycle planning is conducted. Adaptive cycle planning uses project Initiation information,the customer's mission statement ,basic requirements and project constraint to define the set of release cycles that will be required for the project. Collaboration encompasses communication and team-work but it also enphasizes individualism because individual creativity plays an important role in collaborative thinking.It is all above all,a matter of trust. people working together must trust one another to comment without war help without irritation work as hard as ...

Dijkstra's algorithm

Djikstra's algorithm solves the problem of finding the shortest path from a point in a graph (the source ) to a destination. It turns out that one can find the shortest paths from a given source to all points in a graph in the same time, hence this problem is sometimes called the single-source shortest paths problem. This problem is related to the spanning tree one. The graph representing all the paths from one vertex to all the others must be a spanning tree - it must include all vertices. There will also be no cycles as a cycle would define more than one path from the selected vertex to at least one other vertex. For a graph, G = (V,E) where V is a set of vertices and E is a set of edges. Dijkstra's algorithm keeps two sets of vertices: S the set of vertices whose shortest paths from the source have already been determined and V- S : the remaining v...