Help a Thief

Task: A thief wants to steal as much as gold coins from gold mine. In the gold mine N number of gold boxes are there, in every box consisting of  Ai gold plates, with consisting of Aj gold coins in each plate. Find the maximum number of gold coins can thief steal.

Example:

Input:

1

3 // Number of gold plates Thief can steal.

3 // Gold Boxes

1 3 2 2 3 1 // Gold plates and same number of Gold Coins on each plate.

Output:
7

---

Here is the Code:

Program in C++:

1. #include <iostream>
2. using namespace std;
3. int maxPosition(int n,int *a)
4. {
5.     int p,max=0;
6.     for(int i=1;i<n;i=i+2)
7.     {
8.         if(max<a[i])
9.         {
10.             max=a[i];
11.             p=i;
12.         }
13.     }
14.     return p;
15. }
16. int main() {
17. int t;
18. scanf("%d\n",&t);
19. while(t--)
20. {
21.     int nT;
22.     scanf("%d\n",&nT);
23.     int n;
24.     scanf("%d\n",&n);
25.     int a[2*n];
26.     for(int i=0;i<2*n;i++)
27.     {
28.         scanf("%d\n",&a[i]);
29.     }
30.     int p,gc=0;
31.     while(nT!=0)
32.     {
33.         p=maxPosition(2*n,a);
34.         if(nT-a[p-1]>=0)
35.         {
36.             gc+=a[p-1]*a[p];
37.             a[p]=0;
38.             nT-=a[p-1];
39.         }
40.         else
41.         {
42.             gc+=nT*a[p];
43.             nT=0;
44.         }
45.     }
46.     cout<<gc<<endl;
47. }
48. return 0;
49. }

---

Here is the Video: