Algorithm

A. Parkway Walk
time limit per test
1 second
memory limit per test
256 megabytes
Preoblem link- https://codeforces.com/problemset/problem/1697/A
input
standard input
output
standard output

You are walking through a parkway near your house. The parkway has n+1�+1 benches in a row numbered from 11 to n+1�+1 from left to right. The distance between the bench i� and i+1�+1 is ai�� meters.

Initially, you have m� units of energy. To walk 11 meter of distance, you spend 11 unit of your energy. You can't walk if you have no energy. Also, you can restore your energy by sitting on benches (and this is the only way to restore the energy). When you are sitting, you can restore any integer amount of energy you want (if you sit longer, you restore more energy). Note that the amount of your energy can exceed m�.

Your task is to find the minimum amount of energy you have to restore (by sitting on benches) to reach the bench n+1�+1 from the bench 11 (and end your walk).

You have to answer t� independent test cases.

Input

The first line of the input contains one integer t� (1≤t≤1001≤�≤100) — the number of test cases. Then t� test cases follow.

The first line of the test case contains two integers n� and m� (1≤n≤1001≤�≤100; 1≤m≤1041≤�≤104).

The second line of the test case contains n� integers a1,a2,…,an�1,�2,…,�� (1≤ai≤1001≤��≤100), where ai�� is the distance between benches i� and i+1�+1.

Output

For each test case, print one integer — the minimum amount of energy you have to restore (by sitting on benches) to reach the bench n+1�+1 from the bench 11 (and end your walk) in the corresponding test case.

Example
input
Copy
3
3 1
1 2 1
4 5
3 3 5 2
5 16
1 2 3 4 5
output
Copy
3
8
0
Note

In the first test case of the example, you can walk to the bench 22, spending 11 unit of energy, then restore 22 units of energy on the second bench, walk to the bench 33, spending 22 units of energy, restore 11 unit of energy and go to the bench 44.

In the third test case of the example, you have enough energy to just go to the bench 66 without sitting at all.

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;


#define ll long long
#define endl '\n'
#define debug(n) cout<<(n)<<endl;
const ll INF = 2e18 + 99;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int t;
  cin>>t;
  while(t--){
    int n, k;
    cin>>n>>k;
    int x, sum = 0;
    for(int i = 0; i < n; i++){
      cin>>x;
      sum += x;
    }
    if(sum - k <= 0){
      cout<<0<<endl;
    }
    else{
      cout<<(sum-k)<<endl;
    }
  }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
3
3 1
1 2 1
4 5
3 3 5 2
5 16
1 2 3 4 5

Output

x
–
+
cmd
3
8
0
Advertisements

Demonstration

Codeforcess Solution 1697-A A. Parkway Walk ,C++, Java, Js and Python  ,1697-A,Codeforcess Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+