Given street of houses (a row of houses), each house having some amount of money kept inside; now there is a thief who is going to steal this money but he has a constraint/rule that he cannot steal/rob two adjacent houses. Find the maximum money he can rob.
Input:
The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is N and money.
The first line of each test case is N and money.
Output:
Print maximum money he can rob.
Constraints:
1 ≤ T ≤ 100
1 ≤ money ≤ 100
1 ≤ N ≤ 1000
Example:
1 ≤ money ≤ 100
1 ≤ N ≤ 1000
Example:
Input:
2
5 10
2 12
Output:
30
12
Your Code
#include<iostream>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
int ans;
if(n%2==0)
{
ans=(n/2)*m;
}
else
{
ans=(n/2+1)*m;
}
cout<<ans<<endl;
}
return 0;
}