## CPCRC1C - Sum of Digits

Majid is a 3rd-grade elementary student and quite well in mathematics. Once, Majid's teacher asked him to calculate the sum of numbers 1 through n.

Majid quickly answered, and his teacher made him another challenge. He asked Majid to calculate the sum of the digits of numbers 1 through n.

Majid did finally find the solution. Now it is your turn, can you find a solution?

### Input

Two space-separated integers 0 <= a <= b <= 109.

Program terminates if a and b are -1.

### Output

The sum of the digits of numbers a through b.

### Example

`Input:1 10100 777-1 -1Output:468655`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define MOD                 1000000007LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);

const int MAXN = 1e5+5;

string a, b;
ll dp[12][105][2];
int n;

ll solve(string &s, int idx, ll sum, int isPrefixEqual){
if(dp[idx][sum][isPrefixEqual] != -1)
return dp[idx][sum][isPrefixEqual];
ll res = 0;
if(idx == n){
return sum;
}else{
if(isPrefixEqual){
for(int i = 0;i <= s[idx]-'0'; i++){
if(s[idx]-'0' == i)
res += solve(s, idx + 1, sum + i, 1);
else
res += solve(s, idx + 1, sum + i, 0);
}
}else{
for(int i = 0;i <= 9; i++){
res += solve(s, idx + 1, sum + i, 0);
}
}
}
dp[idx][sum][isPrefixEqual] = res;
return res;
}

ll f(string &a){
ll sum = 0;
for(auto c : a){
sum += c - '0';
}
return sum;
}

int main(){
io;
while(1){
cin >> a >> b;
if(a == "-1" && b == "-1")
break;
n = b.size();
memset(dp, -1, sizeof dp);
ll ansR = solve(b, 0, 0, 1);
n = a.size();
memset(dp, -1, sizeof dp);
ll ansL = solve(a, 0, 0, 1);
cout << ansR - ansL + f(a) << endl;
}
return 0;
}``````
Copy The Code &

Input

cmd
1 10
100 777
-1 -1

Output

cmd
46
8655